Submission #1272390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272390		scalifrastico_098	Aliens (IOI16_aliens)	C++20	12 / 100	61 ms	2372 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) {
    sort(r.begin(), r.end()); r.erase(unique(r.begin(), r.end()), r.end());
    if(n==0) return 0; k=min(k, n); 
    vector<vector<long long>> dp(k+1, vector<long long>(n+1, LLONG_MAX));
    dp[0][0]=0;   
    for(long long p=1; p<=k; p++)
    {    
        dp[p][0]=0; 
        for(long long i=1; i<=n; i++)
        {
            long long ans=LLONG_MAX;
            for(int j=1; j<=i; j++)
            {
                if(dp[p-1][j-1]==LLONG_MAX) continue;
                long long gh=(long long)r[i-1]-(long long)r[j-1]+1; long long ghy=gh*gh;
                ans=min(ans, dp[p-1][j-1]+ghy);
            }
            dp[p][i]=ans;
        }
    }
    long long ans=LLONG_MAX;
    for(long long i=1; i<=k; i++)ans=min(ans, dp[i][n]);
    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: 12 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40