Submission #1238744

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

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector <vector <int> > ctl;
    for(int i=0; i<n; ++i){
        if(r[i]>c[i]){
            int aguss=c[i];
            c[i]=r[i];
            r[i]=aguss;
        }
        ctl.push_back({r[i], c[i]});
    }
    sort(ctl.begin(), ctl.end());
    vector <vector <int> > lf;
    int ms=-1;
    for(int i=0; i<n; ++i){
        if(ms<ctl[i][0]){
            ms=-1;
        }
        if(ctl[n-1][0]==ctl[i][0]){
            i=n-1;
        }
        else{
            for(int j=i; j<n-1; ++j){
                if(ctl[j][0]>ctl[i][0]){
                    break;
                }
                i=j;
            }
        }
        if(ctl[i][1]>ms){
            ms=ctl[i][1];
            lf.push_back(ctl[i]);
        }
    }
    n=lf.size();
    long long cost=0;
    long long tmm1=0;
    long long tmm2=0;
    tmm1=lf[0][1]+1-lf[0][0];
    cost+=tmm1*tmm1;
    for(int i=1; i<n; ++i){
        tmm1=lf[i][1]+1-lf[i][0];
        cost+=tmm1*tmm1;
        if(lf[i-1][1]>=lf[i][0]){
            tmm1=lf[i-1][1]-lf[i][0]+1;
            cost-=tmm1*tmm1;
        }
    }
    k-=n;
    while(k<0){
        long long int mn=-1;
        int rw=-1;
        for(int i=1; i<n; ++i){
            tmm1=lf[i][1]-lf[i-1][1];
            tmm2=lf[i][0]-lf[i-1][0];
            if(tmm1*tmm2<mn || mn==-1){
                mn=2*tmm1*tmm2;
                rw=i;
            }
        }
        cost+=mn;
        if(rw==-1){
            return -1;
        }
        lf[rw-1][1]=lf[rw][1];
        lf.erase(lf.begin()+rw, lf.begin()+rw+1);
        ++k;
        --n;
    }
    return cost;
}

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