oj.uz

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 -