Submission #104965

#TimeUsernameProblemLanguageResultExecution timeMemory
104965updown1Aliens (IOI16_aliens)C++17
0 / 100
3 ms384 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define For(i, a, b) for(ll i=a; i<b; i++) #define ffi For(i, 0, n) #define ffj For(j, 0, K) #define ffa ffi ffj #define s <<" "<< //#define c <<" : "<< #define w cout #define e "\n" #define pb push_back #define mp make_pair #define a first #define b second //#define int ll //500,000,000 operations #include "aliens.h" const ll MAXN = 100001, INF = 1000000000000000000; vector<pair<ll, ll> > pts, inp; ll dp[MAXN], cnt[MAXN]; ll calc(ll C) { //w<< "testing" s C<<e; ll len = inp.size(); For (i, 1, len+1) { ll use = INF; ll loc = 0; For (j, 0, i) { ll y = 0; if (j != 0) y = max((ll)0, (inp[j-1].b-inp[j].a+1)*(inp[j-1].b-inp[j].a+1)); ll x = dp[j] + (inp[i-1].b-inp[j].a+1)*(inp[i-1].b-inp[j].a+1) - y + C; //w<< "trying" s j s x<<e; if (x < use) { use = x; loc = j; } } dp[i] = use; cnt[i] = cnt[loc]+1; //w<< i s dp[i] s cnt[i]<<e; } return cnt[inp.size()]; } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { ffi pts.pb(mp(min(r[i], c[i]), max(r[i], c[i]))); sort(pts.begin(), pts.end()); for (auto i: pts) { if (inp.empty()) inp.pb(i); else if (i.b <= inp[inp.size()-1].b) continue; /// don't add it else { while (!inp.empty() && i.a == inp[inp.size()-1].a && i.b >= inp[inp.size()-1].b) inp.pop_back(); inp.pb(i); } } //for (auto i: inp) w<< i.a s i.b<<e; /// binary search on C ll a = 0, b = m*m; while (a != b) { ll mid = (a+b+1)/2; if (calc(mid) > k) a = mid; else b = mid-1; } calc(a); return dp[inp.size()] - cnt[inp.size()]*a; }

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:4:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define For(i, a, b) for(ll i=a; i<b; i++)
                      ^
aliens.cpp:5:13: note: in expansion of macro 'For'
 #define ffi For(i, 0, n)
             ^~~
aliens.cpp:47:5: note: in expansion of macro 'ffi'
     ffi pts.pb(mp(min(r[i], c[i]), max(r[i], c[i]))); sort(pts.begin(), pts.end());
     ^~~
aliens.cpp:47:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     ffi pts.pb(mp(min(r[i], c[i]), max(r[i], c[i]))); sort(pts.begin(), pts.end());
                                                       ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...