Submission #104966

#	Time	Username	Problem	Language	Result	Execution time	Memory
104966		updown1	Aliens (IOI16_aliens)	C++17	0 / 100	3 ms	384 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) {
    //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)/2;
        if (calc(mid) > k) a = mid+1;
        else b = mid;
    }
    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: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: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());
                                                       ^~~~

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