Submission #137908

#	Time	Username	Problem	Language	Result	Execution time	Memory
137908		nash	Aliens (IOI16_aliens)	C++14	0 / 100	2040 ms	504 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;


long long int mnsquares = 1000000000;
vector<int> r, c;
long long int d[501][501];
int n;


//tehere is no point having overlapping squares

//at every point on the diagonal we have 2 choices - start a square here or  not

//if we do, try making the square any size between 1 and thew max

long long int dp(int k, int m, int covered, int idx, vector<int> got, int nogot){
    if (d[k][idx]!=0 && d[k][idx]<covered)
            return d[k][idx];
    if (k<0) return 100000000000;
    if (k==0 || idx==m){
            //if (got==0) return 100000000000;
            if (nogot!=n) return 10000000000;
            //cout << k << ' ' << idx << ' ' << covered << ' ' <<  n << ' ' << nogot << endl;
            return covered;
            //we made it pat the end
    }

    long long int ans = dp(k, m, covered, idx+1, got, nogot);
    //i is size of photo
    for (int i=0;i<=m-idx;i++){
            if (i==0){
                vector<int> newgot=got;
                 int nnogot=nogot;
                for (int a=0;a<n;a++){
                    if (r[a]==idx && c[a]==idx){
                        if (newgot[a]==0) nnogot++;
                        newgot[a]=1;
                    }
                    else if (r[a]<idx && c[a]<idx && newgot[a]==0) return 100000000000000;
                }
                ans=min(ans, dp(k-1, m, covered+1, idx+1, newgot, nnogot));
                continue;
            }
        vector<int> newgot=got;
        int nnogot=nogot;
        for (int a=0;a<n;a++){
            if (r[a]>=idx && r[a]<=idx+i && c[a]>=idx && c[a]<=idx+i){
                if (newgot[a]==0) nnogot++;
                newgot[a]=1;
            }
            else if (r[a]<idx && c[a]<idx && newgot[a]==0) return 100000000000000;
        }
        ans=min(ans, dp(k-1, m, covered+((i+1)*(i+1)), idx+1, newgot, nnogot));
    }
    return d[k][idx]=ans;

}


long long int take_photos(int N, int m, int k, vector<int> R, vector<int> C){
    n=N;
    r=R;
    c=C;
    return dp(k, m, 0, 0, vector<int> (N, 0), 0);

}

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