Submission #1354621
Source Code Expand
#include<stdio.h>
#include<assert.h>
#include<vector>
#include<string.h>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<string>
#include<iostream>
#include<set>
#include<unordered_set>
#include<map>
#include<queue>
#include<functional>
#include<list>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double, double> pdd;
typedef tuple<int,int,int> t3;
const int MX = 200005;
const int MM = 1000000007;
struct UF{
int t[MX], c[MX];
void clear(){
for(int i = 0; i < MX; i++) t[i] = i, c[i] = 1;
}
int find(int a){ return t[a] == a ? a : t[a] = find(t[a]); }
int merge(int a, int b){
a = find(a), b = find(b);
t[a] = b, c[b] += c[a];
}
} uf;
int D[MX], E[MX];
int N;
int main()
{
scanf("%d", &N);
for(int i = 1; i <= N; i++) scanf("%d", D+i), E[i] = i;
sort(E+1, E+N+1, [](int l, int r){ return D[l] > D[r]; });
uf.clear();
ll ans = 0;
for(int i = 1; i <= N; i++){
int c = E[i];
int a = 1, b = 1;
if( c >= 2 && D[c-1] > D[c] ) a += uf.c[uf.find(c-1)], uf.merge(c, c-1);
if( c < N && D[c+1] > D[c] ) b += uf.c[uf.find(c+1)], uf.merge(c, c+1);
ans += (ll)a * b * D[c];
}
printf("%lld\n", ans);
}
Submission Info
Submission Time |
|
Task |
B - Minimum Sum |
User |
zigui |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
1263 Byte |
Status |
AC |
Exec Time |
45 ms |
Memory |
3328 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:45:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
./Main.cpp:46:56: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int i = 1; i <= N; i++) scanf("%d", D+i), E[i] = i;
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0, example1, example2 |
All |
corner0, corner1, corner2, corner3, example0, example1, example2, maxrand0, maxrand1, maxrand2, rand0, rand1, rand2 |
Case Name |
Status |
Exec Time |
Memory |
corner0 |
AC |
26 ms |
3328 KB |
corner1 |
AC |
27 ms |
3328 KB |
corner2 |
AC |
2 ms |
1792 KB |
corner3 |
AC |
41 ms |
3328 KB |
example0 |
AC |
2 ms |
1792 KB |
example1 |
AC |
2 ms |
1792 KB |
example2 |
AC |
2 ms |
1792 KB |
maxrand0 |
AC |
45 ms |
3328 KB |
maxrand1 |
AC |
45 ms |
3328 KB |
maxrand2 |
AC |
45 ms |
3328 KB |
rand0 |
AC |
2 ms |
1792 KB |
rand1 |
AC |
2 ms |
1792 KB |
rand2 |
AC |
2 ms |
1792 KB |