제출 #1307795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307795		thelegendary08	Aliens (IOI16_aliens)	C++17	60 / 100	2108 ms	356932 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
#define int long long
#define f0r(i,n) for(int i = 0; i < n; i++)
#define FOR(i,k,n) for(int i = k; i < n; i++)
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define dout(x); cout<<x<<' '<<#x<<endl;
#define dout2(x,y); cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(v); for(auto u : v)cout<<u<<' '; cout<<endl;
using namespace std;
vi psb; vi a, b; vpii v; vvi dp; 
int intersect(pii &a, pii &b){
	if(a.S<b.F)return 0; else return a.S-b.F+1;
}
int sq(int x){
	return x * x; 
}
int area(int x, int y){
	return a[x] + (psb[y+1]-psb[x+1]);
}
int C(int x, int y){
	return (v[y].S - v[x].F + 1) * (v[y].S - v[x].F + 1) - area(x,y);
}
void solve(int j, int l, int r, int cl, int cr){
	if(l>r)return; int mid = l + r >> 1; int mn = 1e18, mnd = -1; 
	FOR(i,cl,min(mid,cr)+1){
		if(mn > dp[i-1][j-1] + C(i,mid))mn = dp[i-1][j-1] + C(i,mid), mnd = i; 
	}
	dp[mid][j] = mn; solve(j,l,mid-1,cl,mnd); solve(j,mid+1,r,mnd,cr); 
}
long long take_photos(signed n, signed m, signed k, std::vector<signed> r, std::vector<signed> c) {
	vi p(m,-1); f0r(i,n){
		int x = r[i], y = c[i]; if(x > y)swap(x,y); p[x] = max(p[x], y);
		// FOR(a,x,y+1)FOR(b,x,y+1)grid[a][b] = 1; 
	} 
	int mx = -1; f0r(i,m){
		if(p[i] > mx){
			mx=p[i]; v.pb(mp(i,p[i]));
		}
	} n = v.size(); b.pb(0); //for(auto u : v)cout<<u.F<<' '<<u.S<<'\n';
	f0r(i,v.size()){
		a.pb((v[i].S-v[i].F+1)*(v[i].S-v[i].F+1)); 
		if(i!=0)b.pb(a[i] - intersect(v[i-1],v[i]) * intersect(v[i-1],v[i]));
	}
	psb.resize(n+1); FOR(i,1,n+1)psb[i]=psb[i-1]+b[i-1]; 
	int sum = area(0,n-1); dp.resize(n); f0r(i,n)dp[i].resize(k+1,1e18); 
	f0r(i,n)dp[i][1] = C(0,i); 
	FOR(j,2,k+1){
		solve(j,j-1,n-1,j-1,n-1);
	}
	int ans = 4e18; f0r(i,k+1)ans = min(ans, dp[n-1][i]); 
    return ans+sum;
}

컴파일 시 표준 에러 (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: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 0 / 40