Submission #1168222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168222		dnnnda	Aliens (IOI16_aliens)	C++20	25 / 100	126 ms	2432 KiB

aliens

#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
#define init(arr,val) memset(arr,val,sizeof(arr))
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
//const int X=1000000007;
const int X=998244353;

ll dp[505][505];
int l[505], r[505]={-1};

ll take_photos(int n, int m, int K, vector<int> _r, vector<int> _c){
    init(dp,0x3f);
    dp[0][0]=0;
    vector<pair<int,int>> v, v2;
    for(int i=0 ; i<n ; i++){
        if(_r[i]>_c[i]) swap(_r[i],_c[i]);
        v.push_back({_r[i],_c[i]});
    }
    sort(v.begin(),v.end());
    for(int i=0 ; i<n ; i++){
        if(v2.empty()||v[i].S>v2.back().S) v2.push_back(v[i]);
    }
    n=v2.size();
    for(int i=0 ; i<n ; i++) l[i+1]=v2[i].F, r[i+1]=v2[i].S;
    for(int i=1 ; i<=n ; i++) for(int j=1 ; j<=K ; j++){
        for(int k=0 ; k<i ; k++){
            ll len=r[i]-l[k+1]+1;
            ll cov=max(0,r[k]-l[k+1]+1);
            dp[i][j]=min(dp[i][j],dp[k][j-1]+len*len-cov*cov);
        }
        //cout << "dp[" << i << "][" << j << "]=" << dp[i][j] << '\n';
    }
    ll ans=inff;
    for(int j=1 ; j<=K ; j++) ans=min(ans,dp[n][j]);
    return ans;
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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