Submission #1222818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222818		Malix	Aliens (IOI16_aliens)	C++20	0 / 100	0 ms	328 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
#define all(x) (x).begin(),(x).end()
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

long long take_photos(int n, int m, int k, std::vector<int> a, std::vector<int> c) {
    sort(all(a));
    a.erase(unique(all(a)),a.end());
    n=a.size();
    if(k>=n)return (ll)n;
    if(k==1)return (((ll)a[n-1]-(ll)a[0]+1)*((ll)a[n-1]-(ll)a[0]+1));
    ll ans=0;
    vector<pi> b(n);
    vector<ll> val(n,1);
    REP(i,0,n)b[i]={a[i],a[i]};
    while(n>k){
        vector<ll> tmp(n);
        REP(i,0,n-1)tmp[i]=(b[i+1].S-b[i].F+1)*(b[i+1].S-b[i].F+1)-val[i]-val[i+1];
        int pos=0;
        REP(i,1,n-1)if(tmp[i]<tmp[pos])pos=i;
        b[pos].S=b[pos+1].S;
        b.erase(b.begin()+pos+1);
        val[pos]=tmp[pos]+val[pos]+val[pos+1];
        val.erase(val.begin()+pos+1);
        n--;
    }
    REP(i,0,k)ans+=((ll)b[i].S-(ll)b[i].F+1)*((ll)b[i].S-(ll)b[i].F+1);
    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: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40