Submission #105116

#	Time	Username	Problem	Language	Result	Execution time	Memory
105116		updown1	Aliens (IOI16_aliens)	C++17	0 / 100	3 ms	512 KiB

aliens

#include "aliens.h"
#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
const ll MAXN = 100001, INF = 1000000000000000000;
vector<pair<ll, ll> > pts, inp;
ll dp[MAXN], cnt[MAXN];

ll calc(ll C) {
    //if (C == 0) 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 && inp[j-1].b >= inp[j].a ) y = (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;
            //if (C == 0) w<< "trying" s j s y<<e;
            if (x < use || (x == use && cnt[loc] > cnt[j])) {
                use = x;
                loc = j;
            }
        }
        dp[i] = use;
        cnt[i] = cnt[loc]+1;
        //if (C == 7) w<< i s ":" s inp[i-1].a s inp[i-1].b s ":" s dp[i] s cnt[i]<<e;
    }
    //w<< C s cnt[inp.size()]<<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);
        }
        //w<< i.a s i.b<<e;
    }
    //w<<"keep"<<e; 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) b = mid-1;
        else a = mid;
    }
    calc(a); int p1 = cnt[inp.size()]; ll f1 = dp[inp.size()] - a*p1;
    calc(a+1); int p2 = cnt[inp.size()]; ll f2 = dp[inp.size()] - (a+1)*p2;
    //w<< "C:" s a s ":" s p1 s p2<<e;
    return f1 + (f2-f1)/(p2-p1) * (k-p1);
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:5:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define For(i, a, b) for(ll i=a; i<b; i++)
                      ^
aliens.cpp:6:13: note: in expansion of macro 'For'
 #define ffi For(i, 0, n)
             ^~~
aliens.cpp:48: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:48: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());
                                                       ^~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40