Submission #1305298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305298		enzy	Aliens (IOI16_aliens)	C++20	0 / 100	1 ms	348 KiB

aliens

#include<bits/stdc++.h>
#include "aliens.h"
#define ll long long
using namespace std;
const int maxn=510;
const int inf=1000*1000+10;
int dp[maxn][maxn][maxn], ma[maxn][maxn];
int soma_pref(int x){
    return x*(x+1)/2;
}
int soma(int l, int r){
    return soma_pref(r)-soma_pref(l-1);
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
    map<int,int>mp;
    for(int i=0;i<n;i++){
        r[i]++; c[i]++;
        if(r[i]>c[i]) swap(r[i],c[i]);
        mp[r[i]]=max(mp[r[i]],c[i]-r[i]+1);
    }
    vector<int>v, d;
    v.push_back(0); d.push_back(0);
    for(auto [a,b] : mp){
        v.push_back(b); // o tamanho necessario do quadrado
        d.push_back(a); // qual a posicao real dele
    }
    n=v.size()-1;
    for(int i=1;i<=n;i++) ma[i][i]=v[i]+d[i]-1;
    for(int l=2;l<=n;l++){
        for(int i=1;i+l-1<=n;i++){
            int j=i+l-1;
            ma[i][j]=max(ma[i][j-1],ma[j][j]);
        }
    }
    for(int i=0;i<=n;i++)
        for(int j=0;j<=k;j++)
            for(int l=0;l<=n;l++) dp[i][j][l]=inf;
    dp[0][0][0]=0;
    int resp=inf;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            if(i==1) dp[1][1][1]=v[1]*v[1];
            for(int l=1;l<i;l++){
                int aux=ma[l][i-1], at=v[i]+d[i]-1; // quanto o quadrado ja ocupa
                // cout << "? " << i << " " << aux << " " << at << endl;
                if(at<=aux) dp[i][j][l]=dp[i-1][j][l];
                else{
                    int cost=at-aux+2*soma(aux,at-1);
                    // cout << "+" << cost << endl;
                    dp[i][j][l]=dp[i-1][j][l]+cost;
                }
                int bonus=0;
                if(d[i]<aux) bonus=(aux-d[i])*(aux-d[i]); // interseccao
                dp[i][j][i]=min(dp[i][j][i],dp[i-1][j-1][l]+v[i]*v[i]-bonus);
                if(i==n){
                    // cout << "! " << i << " " << j << ' ' << l << ' ' << dp[i][j][l] << endl;
                    resp=min(resp,dp[i][j][l]);
                }
            }
            // cout << "! " << i << " " << j << ' ' << i << ' ' << dp[i][j][i] << endl;
            if(i==n) resp=min(resp,dp[i][j][i]);
        }
    }
    return resp;
}

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: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40