Submission #281727

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
281727	2020-08-23 11:08:27	jun6873	Biochips (IZhO12_biochips)	C++11	100 / 100	66 ms	8908 KiB

biochips

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200004;
int N, K, a[maxn], o;
vector<int> g[maxn];
vector<int> dp(int x) {
  vector<int> res;
  for (int y : g[x]) {
    vector<int> now = dp(y);
    for (int i=now.size()-1; i>=1; i--) now[i] -= now[i-1];
    res.insert(res.end(), now.begin(), now.end());
  }
  sort(res.begin(), res.end());
  reverse(res.begin(), res.end());
  if (res.size() >= K) res.resize(K);
  for (int i=1; i<res.size(); i++) res[i] += res[i-1];
  if (res.empty()) res.push_back(a[x]);
  else res[0] = max(res[0], a[x]);
  return res;
}
int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> N >> K;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

biochips.cpp: In function 'std::vector<int> dp(int)':
biochips.cpp:18:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |  if (res.size() >= K) res.resize(K);
      |      ~~~~~~~~~~~^~~~
biochips.cpp:19:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for (int i=1; i<res.size(); i++) res[i] += res[i-1];
      |                ~^~~~~~~~~~~

• Subtask 1: 100 / 100