oj.uz

Submission #363518

# Submission time Handle Problem Language Result Execution time Memory
363518 2021-02-06T10:44:47 Z ACmachine Bodyguards (CEOI10_bodyguards) C++17
100 / 100
 140 ms 12908 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<str> vstr;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define rsz resize 
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)
	
const double EPS = 1e-9;
const int MOD = 1e9+7; // 998244353;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

#ifdef DEBUG
#define DBG if(1)
#else
#define DBG if(0)
#endif

#define dbg(x) cout << "(" << #x << " : " << x << ")" << endl;
// ostreams
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }
//searches
template<typename T, typename U>
T bsl(T lo, T hi, U f){ hi++; T mid; while(lo < hi){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; }
template<typename U>
double bsld(double lo, double hi, U f, double p = 1e-9){ int r = 3 + (int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid; } return (lo + hi)/2; }
template<typename T, typename U>
T bsh(T lo, T hi, U f){ lo--; T mid; while(lo < hi){ mid = (lo + hi + 1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; }
template<typename U>
double bshd(double lo, double hi, U f, double p = 1e-9){ int r = 3+(int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? lo = mid : hi = mid; } return (lo + hi)/2; }
// some more utility functions
template<typename T>
pair<T, int> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return mp(*it, it - v.begin());}
template<typename T>
pair<T, int> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return mp(*it, it - v.begin());}        
template<typename T> bool ckmin(T& a, const T& b){return b < a ? a = b , true : false;}
template<typename T> bool ckmax(T& a, const T& b){return b > a ? a = b, true : false;}

    
int main(){
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL); cout.tie(NULL);
	int R, C; 
    cin >> R;
    vector<array<ll, 2>> row_groups(R);
    REP(i, R){
        cin >> row_groups[i][0] >> row_groups[i][1];
    }
    cin >> C;
    vector<array<ll, 2>> col_groups(C);
    REP(i, C){
        cin >> col_groups[i][0] >> col_groups[i][1];
    }
    sort(all(col_groups));
    sort(all(row_groups));
    reverse(all(row_groups));
    int pp = 0;
    bool can = true;
    ll sum = 0;
    ll num = 0;
    ll rc = 0;// completed rows;
    ll col_count = 0;
    ll rowsum = 0;
    REP(j, col_groups.size()) col_count += col_groups[j][1];
    REP(j, row_groups.size()){
        rc += row_groups[j][1];
        rowsum += row_groups[j][1] * row_groups[j][0];
        while(pp < col_groups.size() && col_groups[pp][0] < rc){
            num += col_groups[pp][1];
            sum += col_groups[pp][1] * col_groups[pp][0]; 
            pp++;
        } 
        ll globc = sum + (col_count - num) * rc;
        if(globc < rowsum)
            can = false;
    }
    cout << can << "\n";
    

	
    return 0;
}

Compilation message

bodyguards.cpp: In function 'int main()':
bodyguards.cpp:26:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
bodyguards.cpp:28:18: note: in expansion of macro 'FOR'
   28 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
bodyguards.cpp:109:5: note: in expansion of macro 'REP'
  109 |     REP(j, col_groups.size()) col_count += col_groups[j][1];
      |     ^~~
bodyguards.cpp:26:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
bodyguards.cpp:28:18: note: in expansion of macro 'FOR'
   28 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
bodyguards.cpp:110:5: note: in expansion of macro 'REP'
  110 |     REP(j, row_groups.size()){
      |     ^~~
bodyguards.cpp:113:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         while(pp < col_groups.size() && col_groups[pp][0] < rc){
      |               ~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 396 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 236 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 3 ms 492 KB Output is correct
4 Correct 3 ms 492 KB Output is correct
5 Correct 3 ms 620 KB Output is correct
6 Correct 3 ms 620 KB Output is correct
7 Correct 3 ms 620 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 4 ms 620 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 3 ms 620 KB Output is correct
13 Correct 3 ms 620 KB Output is correct
14 Correct 4 ms 652 KB Output is correct
15 Correct 4 ms 620 KB Output is correct
16 Correct 4 ms 620 KB Output is correct
17 Correct 4 ms 620 KB Output is correct
18 Correct 3 ms 620 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2284 KB Output is correct
2 Correct 17 ms 1772 KB Output is correct
3 Correct 28 ms 2796 KB Output is correct
4 Correct 27 ms 2796 KB Output is correct
5 Correct 27 ms 2796 KB Output is correct
6 Correct 33 ms 3308 KB Output is correct
7 Correct 27 ms 2284 KB Output is correct
8 Correct 33 ms 3308 KB Output is correct
9 Correct 30 ms 3180 KB Output is correct
10 Correct 31 ms 3180 KB Output is correct
11 Correct 30 ms 3180 KB Output is correct
12 Correct 33 ms 3308 KB Output is correct
13 Correct 30 ms 3180 KB Output is correct
14 Correct 32 ms 3180 KB Output is correct
15 Correct 32 ms 3308 KB Output is correct
16 Correct 33 ms 3200 KB Output is correct
17 Correct 32 ms 3180 KB Output is correct
18 Correct 32 ms 3180 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 4932 KB Output is correct
2 Correct 43 ms 4204 KB Output is correct
3 Correct 70 ms 5612 KB Output is correct
4 Correct 9 ms 1132 KB Output is correct
5 Correct 74 ms 6252 KB Output is correct
6 Correct 55 ms 4972 KB Output is correct
7 Correct 62 ms 5740 KB Output is correct
8 Correct 8 ms 1004 KB Output is correct
9 Correct 66 ms 6252 KB Output is correct
10 Correct 62 ms 5868 KB Output is correct
11 Correct 61 ms 5868 KB Output is correct
12 Correct 60 ms 5868 KB Output is correct
13 Correct 68 ms 6380 KB Output is correct
14 Correct 68 ms 6084 KB Output is correct
15 Correct 66 ms 6124 KB Output is correct
16 Correct 64 ms 6124 KB Output is correct
17 Correct 66 ms 6124 KB Output is correct
18 Correct 69 ms 6124 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 8940 KB Output is correct
2 Correct 96 ms 8684 KB Output is correct
3 Correct 87 ms 7916 KB Output is correct
4 Correct 34 ms 3308 KB Output is correct
5 Correct 104 ms 9580 KB Output is correct
6 Correct 109 ms 12908 KB Output is correct
7 Correct 76 ms 7020 KB Output is correct
8 Correct 103 ms 9196 KB Output is correct
9 Correct 124 ms 11500 KB Output is correct
10 Correct 132 ms 11284 KB Output is correct
11 Correct 126 ms 11500 KB Output is correct
12 Correct 123 ms 11356 KB Output is correct
13 Correct 123 ms 11500 KB Output is correct
14 Correct 12 ms 1516 KB Output is correct
15 Correct 139 ms 12140 KB Output is correct
16 Correct 140 ms 12140 KB Output is correct
17 Correct 135 ms 12140 KB Output is correct
18 Correct 122 ms 11372 KB Output is correct