Submission #777674

#	Time	Username	Problem	Language	Result	Execution time	Memory
777674		79brue	Card Scoring (CCO19_day2problem1)	C++17	6 / 100	354 ms	42200 KiB

Main

#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 (stderr)

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
• Subtask 2: 1 / 1
• Subtask 3: 5 / 5
• Subtask 4: 0 / 3
• Subtask 5: 0 / 3
• Subtask 6: 0 / 9