Submission #293598

#	Time	Username	Problem	Language	Result	Execution time	Memory
293598		daniel920712	Aliens (IOI16_aliens)	C++14	0 / 100	2069 ms	1184 KiB

aliens

#include "aliens.h"
#include <algorithm>
using namespace std;
struct A
{
    int a;
    int b;
}Node[100005];
long long DP[4005][4005]={0};
bool have[4005][4005];
bool cmp(A a,A b)
{
    return a.a<b.a||a.a==b.a&&a.b<b.b;
}
long long F(int N,int M)
{
    long long i;
    if(N==-1) return 0;
    if(M==0) return 1e18;
    if(have[N][M]) return DP[N][M];
    DP[N][M]=1e18;
    for(i=N;i>=0;i--) DP[N][M]=min(DP[N][M],F(i-1,M-1)+(Node[N].a-min(Node[i].b,Node[i].b)+1)*(Node[N].a-min(Node[i].b,Node[i].b)+1)-max(0,Node[N].a-Node[N+1].b)*max(0,Node[N].a-Node[N+1].b));
    //printf("%d %d %lld\n",N,M,DP[N][M]);
    return DP[N][M];

}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
    int i;
    for(i=0;i<n;i++)
    {
        Node[i].a=max(r[i],c[i]);
        Node[i].b=min(r[i],c[i]);
    }
    sort(Node,Node+n,cmp);
    Node[n].b=1e9;
    //for(i=0;i<n;i++) printf("%d %d\n",Node[i].a,Node[i].b);

    return F(n-1,k);
}

Compilation message (stderr)

aliens.cpp: In function 'bool cmp(A, A)':
aliens.cpp:13:29: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   13 |     return a.a<b.a||a.a==b.a&&a.b<b.b;
      |                     ~~~~~~~~^~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40