Submission #1176090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176090		AlgorithmWarrior	Aliens (IOI16_aliens)	C++20	25 / 100	32 ms	9284 KiB

aliens

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

using namespace std;

struct interval{
    int l,r;
    bool operator<(interval ot){
        if(l!=ot.l)
            return l<ot.l;
        return r>ot.r;
    }
}intv[100005];

long long diag[1000005];

void maxself(long long& x,long long val){
    if(x<val)
        x=val;
}

void minself(long long& x,long long val){
    if(x>val)
        x=val;
}

long long p2(int nr){
    return 1LL*nr*nr;
}

long long take_photos(int n,int m,int k,vector<int>r,vector<int>c){
    int i,j;
    for(i=0;i<2*m-1;++i)
        diag[i]=-1;
    for(i=0;i<n;++i){
        int lin=r[i];
        int col=c[i];
        maxself(diag[lin+col],abs(lin-col));
    }
    int total=0;
    for(i=0;i<2*m-1;++i)
        if(diag[i]>-1)
            intv[++total]={(i-diag[i])/2,(i+diag[i])/2+1};
    sort(intv+1,intv+total+1);
    int new_total=0;
    intv[0]={-1,-1};
    for(i=1;i<=total;++i)
        if(intv[new_total].r<intv[i].r)
            intv[++new_total]=intv[i];
    total=new_total;
    vector<vector<long long>>dp(total+5,vector<long long>(k+5,1e18));
    for(i=1;i<=total;++i)
        dp[i][1]=p2(intv[i].r-intv[1].l);
    int lst;
    if(k>total)
        k=total;
    for(j=2;j<=k;++j)
        for(i=j;i<=total;++i)
            for(lst=j-1;lst<i;++lst)
                minself(dp[i][j],p2(intv[i].r-intv[lst+1].l)-p2(max(0,intv[lst].r-intv[lst+1].l))+dp[lst][j-1]);
    return dp[total][k];
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:43:39: warning: narrowing conversion of '((((long long int)i) - diag[i]) / 2)' from 'long long int' to 'int' [-Wnarrowing]
   43 |             intv[++total]={(i-diag[i])/2,(i+diag[i])/2+1};
      |                            ~~~~~~~~~~~^~
aliens.cpp:43:55: warning: narrowing conversion of '(((((long long int)i) + diag[i]) / 2) + 1)' from 'long long int' to 'int' [-Wnarrowing]
   43 |             intv[++total]={(i-diag[i])/2,(i+diag[i])/2+1};
      |                                          ~~~~~~~~~~~~~^~
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