Submission #1256993

#TimeUsernameProblemLanguageResultExecution timeMemory
1256993MingyuanzAliens (IOI16_aliens)C++20
12 / 100
96 ms2380 KiB
#include "aliens.h" #include <bits/stdc++.h> #define pb push_back #define pii pair<Int,Int> #define f first #define s second #define INF (int)1e17 #define MOD (int)(1e9+7) #define MAXN 100005 #define enl '\n' #define DB(CODE) cout<<'\t'<<CODE<<'\n'; #define SP <<' '<< #define Int long long typedef long long ll; using namespace std; long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { pii arr[n]; for(int i=0; i<n; i++) arr[i]={r[i],c[i]}; sort(arr,arr+n,[](pii a,pii b){return a.f+a.s<b.f+b.s;}); Int dp[k+1][n+1]; for(Int i=0; i<=k; i++) for(Int j=0; j<=n; j++) dp[i][j]=INF; dp[0][0]=0; for(Int i=1; i<=n; i++) for(Int c=1; c<=k; c++){ Int mx=-INF,mn=INF; for(Int j=i; j>0; j--){ mx=max(mx,max(arr[j-1].f,arr[j-1].s)); mn=min(mn,min(arr[j-1].f,arr[j-1].s)); dp[c][i]=min(dp[c][i],dp[c-1][j-1]+(mx-mn+1)*(mx-mn+1)); } } Int ans=INF; for(Int i=0; 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
      |         ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...