oj.uz

Submission #940906

# Submission time Handle Problem Language Result Execution time Memory
940906 2024-03-08T02:00:03 Z imarn Aliens (IOI16_aliens) C++14
12 / 100
 2 ms 448 KB 
#include<bits/stdc++.h>
//#include "game.h"
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<pii>
using namespace std;
struct deal{
    ll x,y,z;
};
long double slope(deal x,deal y){
    return ((long double)x.y-y.y)/(y.x-x.x);
}
pll dp[100005];
vector<pll>pt;
pll solve(ll x,int n){
    deque<deal>dq;dq.pb({-2*(pt[0].f-1),(pt[0].f-1)*(pt[0].f-1),0});
    for(int i=0;i<n;i++){
        while(dq.size()>1&&slope(dq[0],dq[1])<pt[i].s)dq.pop_front();
        dp[i] = {dq[0].x*pt[i].s+pt[i].s*pt[i].s+dq[0].y+x,dq[0].z+1};
        if(i==n-1)continue;deal tmp = {-2*(pt[i+1].f-1),(pt[i+1].f-1)*(pt[i+1].f-1)+dp[i].f-max(1ll*0,pt[i].s-pt[i+1].f+1)*max(1ll*0,pt[i].s-pt[i+1].f+1),dp[i].s};
        while(dq.size()>1&&slope(dq[dq.size()-2],dq.back())>slope(dq.back(),tmp))dq.pop_back();
        dq.pb(tmp);
    }return dp[n-1];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    for(int i=0;i<n;i++){
        if(r[i]>c[i])swap(r[i],c[i]);
        pt.pb({c[i],r[i]});
    }sort(all(pt));
    stack<pll>st;
    for(auto it : pt){
        while(!st.empty()&&(st.top().s>=it.s||st.top().f==it.f))st.pop();
        st.push(it);
    }n=st.size();while(!pt.empty())pt.pop_back();
    while(!st.empty())pt.pb({st.top().s,st.top().f}),st.pop();
    reverse(all(pt));ll le=0,re=1e18;
    while(le<re){
        ll md=(le+re)>>1;
        if(solve(md,n).s<=k)re=md;
        else le=md+1;
    }return solve(le,n).f-le*k;
}

Compilation message

aliens.cpp: In function 'std::pair<long long int, long long int> solve(long long int, int)':
aliens.cpp:27:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   27 |         if(i==n-1)continue;deal tmp = {-2*(pt[i+1].f-1),(pt[i+1].f-1)*(pt[i+1].f-1)+dp[i].f-max(1ll*0,pt[i].s-pt[i+1].f+1)*max(1ll*0,pt[i].s-pt[i+1].f+1),dp[i].s};
      |         ^~
aliens.cpp:27:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   27 |         if(i==n-1)continue;deal tmp = {-2*(pt[i+1].f-1),(pt[i+1].f-1)*(pt[i+1].f-1)+dp[i].f-max(1ll*0,pt[i].s-pt[i+1].f+1)*max(1ll*0,pt[i].s-pt[i+1].f+1),dp[i].s};
      |                            ^~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct answer: answer = 4
2 Correct 0 ms 348 KB Correct answer: answer = 4
3 Incorrect 0 ms 344 KB Wrong answer: output = 1, expected = 4
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct answer: answer = 1
2 Correct 0 ms 348 KB Correct answer: answer = 4
3 Correct 0 ms 348 KB Correct answer: answer = 1
4 Correct 0 ms 344 KB Correct answer: answer = 5
5 Correct 0 ms 344 KB Correct answer: answer = 41
6 Correct 0 ms 348 KB Correct answer: answer = 71923
7 Correct 1 ms 348 KB Correct answer: answer = 77137
8 Correct 1 ms 348 KB Correct answer: answer = 764
9 Correct 2 ms 344 KB Correct answer: answer = 250000
10 Correct 1 ms 344 KB Correct answer: answer = 500
11 Correct 0 ms 348 KB Correct answer: answer = 32
12 Correct 1 ms 348 KB Correct answer: answer = 130050
13 Correct 1 ms 348 KB Correct answer: answer = 5110
14 Correct 1 ms 444 KB Correct answer: answer = 2626
15 Correct 1 ms 348 KB Correct answer: answer = 796
16 Correct 1 ms 360 KB Correct answer: answer = 7580
17 Correct 1 ms 348 KB Correct answer: answer = 1904
18 Correct 1 ms 448 KB Correct answer: answer = 996004
19 Correct 2 ms 348 KB Correct answer: answer = 38817
20 Correct 1 ms 348 KB Correct answer: answer = 4096
21 Correct 1 ms 348 KB Correct answer: answer = 1
22 Correct 0 ms 440 KB Correct answer: answer = 1
23 Correct 1 ms 348 KB Correct answer: answer = 2040
24 Correct 1 ms 348 KB Correct answer: answer = 2

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct answer: answer = 4
2 Correct 0 ms 348 KB Correct answer: answer = 4
3 Incorrect 0 ms 344 KB Wrong answer: output = 1, expected = 4
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct answer: answer = 4
2 Correct 0 ms 348 KB Correct answer: answer = 4
3 Incorrect 0 ms 344 KB Wrong answer: output = 1, expected = 4
4 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct answer: answer = 4
2 Correct 0 ms 348 KB Correct answer: answer = 4
3 Incorrect 0 ms 344 KB Wrong answer: output = 1, expected = 4
4 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Correct answer: answer = 4
2 Correct 0 ms 348 KB Correct answer: answer = 4
3 Incorrect 0 ms 344 KB Wrong answer: output = 1, expected = 4
4 Halted 0 ms 0 KB -