제출 #1305781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305781		thelegendary08	Aliens (IOI16_aliens)	C++17	25 / 100	869 ms	1114112 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;
vvi ps; 
int sq(int x){
	return x * x; 
}
int sm(int x, int y){
	return ps[y+1][y+1]-ps[x][y+1]-ps[y+1][x]+ps[x][x];
}

long long take_photos(signed n, signed m, signed k, std::vector<signed> r, std::vector<signed> c) {
	vi p(m,-1); vector<vector<bool>>grid(m, vector<bool>(m)); 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; vpii v; f0r(i,m){
		if(p[i] > mx){
			mx=p[i]; v.pb(mp(i,p[i]));
		}
	} n = v.size(); //for(auto u : v)cout<<u.F<<' '<<u.S<<'\n';
	ps.resize(m+1); f0r(i,m+1)ps[i].resize(m+1);
	FOR(i,1,m+1)FOR(j,1,m+1)ps[i][j]=ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1]+grid[i-1][j-1];
	int sum = ps[m][m]; vvi dp(n,vi(k+1,1e18)); f0r(i,n){
		dp[i][1] = sq(v[i].S-v[0].F+1) - sm(v[0].F,v[i].S); 
		FOR(j,1,i+1){
			int cost = sq(v[i].S-v[j].F+1) - sm(v[j].F,v[i].S); 
			FOR(l,2,k+1)dp[i][l] = min(dp[i][l], dp[j-1][l-1] + cost);
		}
	} 
	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: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40