Submission #138339

#	Time	Username	Problem	Language	Result	Execution time	Memory
138339		Runtime_error_	Aliens (IOI16_aliens)	C++14	0 / 100	5 ms	504 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf = 5e4+9,K = 109,MX = 1e18+9;

ll sqr(ll x){
    return x*x;
}

ll dp[K][inf];
pair<ll,ll> a[inf];
vector<pair<ll,ll> > all;

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {

    for(int i=0;i<n;i++)
        r[i]++,c[i]++,
        all.push_back( make_pair(min(r[i],c[i]),-max(r[i],c[i])) );

    sort(all.begin(),all.end());
    n = 1;
    a[n] = all[0];
    for(int i=1;i<all.size();i++){
        auto o = all[i];
        if(o.second <= a[n].second)
           continue;
        a[++n] = make_pair(o.first,-o.second);
    }
    for(int i=1;i<=n;i++)
        assert(a[i].first >= a[i-1].first && a[i].second >= a[i-1].second);
    memset(dp,61,sizeof(dp));
    for(int i=0;i<=k;i++)
        dp[i][0] = 0;

    for(ll j=1;j<=k;j++)
        for(ll i=1;i<=n;i++)
                for(ll z = 1;z<=i;z++)
                    dp[j][i] = min( dp[j][i] , dp[j-1][z-1] + sqr(a[i].second - a[z].first+1) - sqr(max(0ll,a[z-1].second - a[z].first+1)) );

    return dp[k][n];
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<all.size();i++){
                 ~^~~~~~~~~~~

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