Submission #1257344

#TimeUsernameProblemLanguageResultExecution timeMemory
1257344MingyuanzAliens (IOI16_aliens)C++20
60 / 100
2116 ms648264 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 MAXV 1000005 #define enl '\n' #define DB(CODE) cout<<'\t'<<CODE<<'\n'; #define SP <<' '<< #define Int long long typedef long long ll; using namespace std; Int power2(Int x){ return x*x; } struct line{ Int m,c; Int val(Int x){ return m*x+c; } }; line defln={0,INF}; struct node{ line ln; node *l,*r; }; node *createnode(line ln){ node *nd=(node*)malloc(sizeof(node)); nd->ln=ln; nd->l=nd->r=NULL; return nd; } void insert(node *&root,line ln,Int l=0,Int r=MAXV){ if(!root) root=createnode(defln); Int m=(l+r)/2; if(ln.val(m)<(root->ln).val(m)) swap(root->ln,ln); if(l<r && ln.val(l)<(root->ln).val(l)) insert(root->l,ln,l,m); if(l<r && ln.val(r)<(root->ln).val(r)) insert(root->r,ln,m+1,r); } Int query(node *&root,Int x,Int l=0,Int r=MAXV){ if(!root) return INF; Int m=(l+r)/2; if(x<=m) return min((root->ln).val(x),query(root->l,x,l,m)); else return min((root->ln).val(x),query(root->r,x,m+1,r)); } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { vector<pii> inp(n),arr={{-1,-1}}; for(Int i=0; i<n; i++) inp[i]={min(r[i],c[i]),max(r[i],c[i])}; sort(inp.begin(),inp.end(),[](pii a,pii b){return a.f<b.f || (a.f==b.f && a.s>b.s);}); for(auto p: inp){ if(p.s<=arr.back().s) continue; arr.pb(p); } n=arr.size()-1; 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; node *root[k+1]={NULL}; insert(root[0],{-2*(arr[1].f-1),power2(arr[1].f-1)}); for(Int i=1; i<=n; i++) for(Int c=1; c<=k; c++){ dp[c][i]=min(power2(arr[i].s)+query(root[c-1],arr[i].s),INF); if(i<n) insert(root[c],{-2*(arr[i+1].f-1),dp[c][i]+power2(arr[i+1].f-1)-power2(max(arr[i].s-arr[i+1].f+1,0ll))}); } 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...