Submission #1036977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036977		aaaaaarroz	Aliens (IOI16_aliens)	C++17	60 / 100	2039 ms	54916 KiB

aliens

    #include <bits/stdc++.h>
    #define ent '\n'
    #define line pair<ll, ll>
    #define k first
    #define b second
     
    typedef long long ll;
    using namespace std;
    const int maxn = 1e6+12;
     
    vector<int> g[maxn];
    bool was[maxn];
    ll dp[maxn];
    ll ndp[maxn];
    int L[maxn];
    int R[maxn];
     
    bool check(line nw, line last, line prl){
        if((nw.b - prl.b) * (prl.k - last.k) <= (last.b - prl.b) * (prl.k - nw.k))return 1;
        return 0;
    }
     
    int ptr = 0;
    vector<line> l;
    void add(line x){
        while(l.size() && l.back().k == x.k && l.back().b > x.b){
            l.pop_back();
        }
        if(l.size() && l.back().k == x.k && l.back().b <= x.b){
            return;
        }
        while(l.size()>1 && check(x, l.back(), l[l.size()-2])){
            l.pop_back();
        }
        l.push_back(x);
    }
    ll get(ll x){
        if(!l.size()){
            return 1e12+1;
        }
        if(ptr >= l.size()){
            ptr = l.size()-1;
        }
        while(ptr + 1 < l.size() && l[ptr].k * x + l[ptr].b > l[ptr+1].k * x + l[ptr+1].b){
            ptr++;
        }
        return l[ptr].k * x + l[ptr].b;
    }
     
    long long take_photos(int n, int m, int k, vector<int> r, vector<int> c){
        for(int i=1;i<=m;i++){
            L[i] = 1e9;
        }
        m = 0;
        for(int i=0;i<n;i++){
            if(r[i] < c[i]){
                swap(r[i], c[i]);
            }
            r[i]++, c[i]++;
            L[r[i]] = min(L[r[i]], c[i]);
            R[c[i]] = max(R[c[i]], r[i]);
            for(int x=-1;x<=0;x++){
                was[r[i]+x] = was[c[i]+x] = 1;
            }
            m = max(m, r[i]);
        }
        was[1] = 1;
        vector<int> t;
        for(int i=1;i<=m;i++){
            dp[i] = ndp[i] = 1e12+1;
            R[i] = max(R[i], R[i-1]);
            if(!was[i]) continue;
            t.push_back(i);
            g[max(R[i], i)].push_back(i);
        }
        for(int _=1;_<=k;_++){
            add({0, 0});
            for(int &i:t){
                ndp[i] = get(i) + i * 1ll * i;
                for(int &j:g[i]){
                    ll b = j * 1ll * j + dp[R[j]];
                    if(R[j] > j) b -= (R[j] - j) * 1ll * (R[j] - j);
                    add(line(-2 * j, b));
                }
            }
            for(int &i:t){
                dp[i] = ndp[i];
            }
            ptr = 0;
            l.clear();
        }
        return dp[m];
    }

Compilation message (stderr)

aliens.cpp: In function 'll get(ll)':
aliens.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         if(ptr >= l.size()){
      |            ~~~~^~~~~~~~~~~
aliens.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         while(ptr + 1 < l.size() && l[ptr].k * x + l[ptr].b > l[ptr+1].k * x + l[ptr+1].b){
      |               ~~~~~~~~^~~~~~~~~~

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