oj.uz

답안 #1085555

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1085555 2024-09-08T12:00:28 Z Sunbae 바이오칩 (IZhO12_biochips) C++17
10 / 100
 365 ms 524288 KB 
#include <bits/stdc++.h>
#define z exit(0)
using namespace std;
const int N = 2e5 + 5, inf = 2e8;
vector<int> g[N];
int x[N], tin[N], tout[N], timer = 1, V[N], dp[N][501], mx[501][N];
void dfs(int u){
	tin[u] = timer++;
	for(int v: g[u]) dfs(v);
	tout[u] = timer++;
}
bool cmp(int i, int j){ return tout[i] < tout[j]; }
signed main(){
	int n, m, r = 0; scanf("%d %d", &n, &m);
	for(int v = 0, u; v<n; ++v){
		scanf("%d %d", &u, x+v); --u; 
		if(u != -1) g[u].push_back(v);
		else r = v;
		V[v] = v;
		fill(dp[v], dp[v]+m+1, -inf);
	}
	dfs(r);
	sort(V, V+n, cmp);
	mx[0][0] = dp[0][0] = 0;
	mx[1][0] = dp[0][1] = x[V[0]];
	int ans = dp[0][m];
	for(int i = 1; i<n; ++i){
		int low = 0, high = i-1, idx = -1;
		while(low <= high){
			int mid = low + ((high-low)>>1);
			if(tout[V[mid]] < tin[V[i]]) low = mid+1, idx = mid;
			else high = mid-1;
		}
		for(int k = 0; k<=m; ++k){
			dp[i][k] = max(dp[i][k], dp[i-1][k]);
			if(idx != -1) dp[i][k] = max(dp[i][k], mx[k-1][idx] + x[V[i]]);
			mx[k][i] = dp[i][k];
		}	
		ans = max(ans, dp[i][m]);
		for(int k = 0; k<=m; ++k) mx[k][i] = max(mx[k][i], mx[k][i-1]);
	}
	assert(ans == mx[m][n-1]); 
	printf("%d", mx[m][n-1]);
}

Compilation message

biochips.cpp: In function 'int main()':
biochips.cpp:14:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  int n, m, r = 0; scanf("%d %d", &n, &m);
      |                   ~~~~~^~~~~~~~~~~~~~~~~
biochips.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |   scanf("%d %d", &u, x+v); --u;
      |   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Incorrect 2 ms 4956 KB Output isn't correct
3 Incorrect 2 ms 5468 KB Output isn't correct
4 Incorrect 14 ms 25176 KB Output isn't correct
5 Incorrect 18 ms 28448 KB Output isn't correct
6 Incorrect 20 ms 29528 KB Output isn't correct
7 Incorrect 348 ms 474140 KB Output isn't correct
8 Incorrect 362 ms 474140 KB Output isn't correct
9 Runtime error 365 ms 524288 KB Execution killed with signal 9
10 Runtime error 364 ms 524288 KB Execution killed with signal 9