## Submission #777674

# Submission time Handle Problem Language Result Execution time Memory
777674 2023-07-09T12:50:25 Z 79brue Card Scoring (CCO19_day2problem1) C++17
6 / 100
354 ms 42200 KB
```#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const double eps = 1e-9;

int k;

inline double pow(ll x){
return k==4 ? x*x : x*sqrt(x);
}

struct dat{
ll x; double y;
dat(){}
dat(ll x, double y): x(x), y(y){} /// 원점에 해당하는 (x, y)

double get(ll v){
return pow(v-x+1)+y;
}
};

int n;
int arr[1000002];
int ord[1000002], cnt[1000002];
vector<dat> vec[1000002];
double DP[1000002];

ll cross(dat &a, dat &b, ll x){ /// a보다 b가 더 크게 되는 시점
ll L=x, R=n, ANS=x-1;
while(L<=R){
ll M=(L+R)/2;
if(a.get(M)<=b.get(M)) ANS=M, R=M-1;
else L=M+1;
}
return ANS;
}

void append(int v, ll x, double y){
dat p (x, y);
if(!vec[v].empty() && p.get(x) <= vec[v].back().get(x)) return;
while(!vec[v].empty() && cross(p, vec[v].back(), x) >= cross(p, vec[v][(int)vec[v].size()-2], x)) vec[v].pop_back();
vec[v].push_back(p);
}

double calc(int v, ll x){
while((int)vec[v].size() >= 2 && vec[v].back().get(x) <= vec[v][(int)vec[v].size()-2].get(x)) vec[v].pop_back();
return vec[v].back().get(x);
}

int main(){
scanf("%d %d", &k, &n);
for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
if(k==2){
printf("%d", n);
return 0;
}

for(int i=1; i<=n; i++){
ord[i] = ++cnt[arr[i]];
DP[i] = DP[i-1];
append(arr[i], ord[i], DP[i-1]);
DP[i] = max(DP[i], calc(arr[i], ord[i]));
//        printf("%d: %.9f\n", i, DP[i]);
}
printf("%.9f", DP[n]);
}
```

### Compilation message

```Main.cpp: In function 'int main()':
Main.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 |     scanf("%d %d", &k, &n);
|     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:54:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
|                             ~~~~~^~~~~~~~~~~~~~~```

#### Subtask #1 0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23796 KB Output isn't correct
2 Halted 0 ms 0 KB -

#### Subtask #2 1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23800 KB Output is correct
3 Correct 11 ms 23708 KB Output is correct

#### Subtask #3 5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23800 KB Output is correct
3 Correct 11 ms 23708 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 11 ms 23800 KB Output is correct
6 Correct 11 ms 23708 KB Output is correct
7 Correct 12 ms 23800 KB Output is correct
8 Correct 13 ms 23804 KB Output is correct
9 Correct 12 ms 23804 KB Output is correct

#### Subtask #4 0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 11 ms 23800 KB Output is correct
3 Correct 11 ms 23708 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 11 ms 23800 KB Output is correct
6 Correct 11 ms 23708 KB Output is correct
7 Correct 12 ms 23800 KB Output is correct
8 Correct 13 ms 23804 KB Output is correct
9 Correct 12 ms 23804 KB Output is correct
10 Incorrect 14 ms 23788 KB Output isn't correct
11 Halted 0 ms 0 KB -

#### Subtask #5 0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 41436 KB Output is correct
2 Incorrect 233 ms 42200 KB Output isn't correct
3 Halted 0 ms 0 KB -

#### Subtask #6 0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23796 KB Output isn't correct
2 Halted 0 ms 0 KB -