1203
//int n,k; //int kk[50]; //int m[10100] = {0}; //cin >> n >> k; //FOR(i,k) // cin >> kk[i]; //int t = *min_element(kk, kk+k); //m[t] = 1; //FOR(i,n) //{ // FOR(j,k) // { // // } //} #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <math.h> #include <limits.h> using namespace std; // Datatypes typedef vector<int> vi; typedef vector<string> vs; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef long long ll; typedef long double ld; // Define #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define FOR(_i,_n) for(int (_i) = 0; (_i) < (_n); (_i)++) #define mp make_pair // Constants const double eps = 1e-8; const double PI = 3.1415926535897932384626433832795; #define INPUT_FILE "xo.in" #define OUTPUT_FILE "xo.out" vector< pair<ii, int> > v; vector< bool > s; vector< int > res; void GreedyActivitySelector() { int j = -1; FOR(i,sz(v)) { if(s[i] == false) { j = i; break; } } if(j == -1) return; s[j] = true; res.pb(v[j].second); for(int i = j + 1; i < sz(v); i++) { if(s[i] == false) { // >= - если нет промежутка между заявками // > - если есть if(v[i].first.second > v[j].first.first) { res.pb(v[i].second); s[i] = true; j = i; } } } } int main(void) { #ifdef ALEX freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else //freopen(INPUT_FILE, "r", stdin); //freopen(OUTPUT_FILE, "w", stdout); #endif int n,m,k,p; //cin >> n >> m >> k >> p; cin >> k; p = 1; m = 1; s.resize(k); FOR(i,k) { int s,f; cin >> s >> f; v.pb(mp(mp(f,s), i+1)); } sort(v.begin(), v.end()); FOR(i,m) GreedyActivitySelector(); cout << sz(res) * p << endl; /* FOR(i,sz(res)) cout << res[i] << " "; */ return 0; }
page revision: 0, last edited: 05 May 2007 20:56