Submission #1156125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156125		Samuraj	Aliens (IOI16_aliens)	C++20	25 / 100	89 ms	8516 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define irep(i,a,b) for(int i = a; i >= b; i--)
typedef long long ll;
typedef long double ld;
//typedef __int128 int128;
typedef vector<int> vi;
typedef pair<int,int> pi; 
typedef pair<double,double> pd;
typedef pair<ll,ll> pl;

const int max_n = 1007;
const ll INF = 1e12+7;

struct seg{
    ll beg;
    ll end;
    ll a;
    ll b;
    ll k;
};

pl arr[max_n];
ll odj[max_n]; //stale!
ll dp[max_n][max_n];

vector<pl> points; //do pierwszego sortu!

ll take_photos(int n, int m, int k, vi row, vi col){
    //ustawic nowe n!
    rep(i,0,n-1){
        if(col[i] < row[i]){
            //przestawienie na gorna polowe!
            int diff = row[i]-col[i];
            col[i] += diff;
            row[i] -= diff;
        }
        //cout << "i: " << i << " point: " << row[i] << ' ' << col[i] << '\n';
        points.pb({row[i],col[i]});
    }
    sort(points.begin(),points.end());

    int akt_ind = 0;
    ll max_c = -1;
    rep(i,0,n-1){
        if(points[i].nd <= max_c) continue; //jest dalej mniejsze h!
        if(i != n-1 && points[i+1].st == points[i].st) continue; //ten sam rząd
        arr[++akt_ind] = points[i];
        max_c = points[i].nd;
    }

    //policzyc odj!
    rep(i,2,akt_ind){
        if(arr[i].st > arr[i-1].nd) continue;
        ll val = arr[i-1].nd-arr[i].st+1;
        odj[i] = val*val;
    }

    /* rep(i,1,akt_ind){
        cout << "i: " << i << " arr: " << arr[i].st << ' ' << arr[i].nd << " odj: " << odj[i] << '\n';
    } */

    k = min(k,akt_ind); //wazne, zeby za duzo prostokatow nie robic!!!

    rep(i,0,n) rep(j,0,n) dp[i][j] = INF;
    dp[0][0] = 0;
    rep(i,1,akt_ind)
        rep(j,1,k)
            rep(prev,1,i){
                ll val = (arr[i].nd-arr[prev].st+1)*(arr[i].nd-arr[prev].st+1);
                //cout << "i: " << i << " j: " << j << " prev: " << prev << " val: " << val << '\n';
                dp[i][j] = min(dp[i][j],dp[prev-1][j-1]+val-odj[prev]);
                //cout << "dp: " << dp[i][j] << '\n';
            }
    

    ll ans = dp[akt_ind][k];
    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