Submission #866216
Source Code Expand
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
int N;
long long x;
vector<int> vec;
const int MAX_S = 5000;
struct SparseTable {
static const int LOG_MAX_S = 14;
int st[LOG_MAX_S][MAX_S*2];
int ln[MAX_S];
void init(const vector<int> &vec) {
for (int i = 0; i < MAX_S; ++i) {
st[0][i] = 1<<30;
int ti = i, tln = 0;
while (ti > 0) ti /= 2, ++tln;
ln[i] = tln - 1;
}
for (int i = 0; i < vec.size(); ++i) st[0][i] = vec[i];
for (int i = 1; i < LOG_MAX_S; ++i) {
for (int j = 0; j < MAX_S; ++j) {
st[i][j] = min(st[i-1][j], st[i-1][j + (1<<(i-1))]);
}
}
}
// [a, b)
int get(int a, int b) {
if (a >= b) return 1<<30;
int bet = b - a, row = ln[bet];
return min(st[row][a], st[row][b - (1<<row)]);
}
} st;
long long solve() {
long long res = 1LL<<59;
st.init(vec);
for (int con = 0; con < N; ++con) {
long long tmp = x * con;
for (int i = 0; i < N; ++i) {
int Min = 1<<30;
if (con <= i) chmin(Min, st.get(i-con, i+1));
else {
chmin(Min, st.get(0, i+1));
chmin(Min, st.get(N-(con-i), N));
}
//cout << con << ", " << i << ": " << Min << endl;
tmp += Min;
}
//cout << tmp << endl << endl;
chmin(res, tmp);
}
return res;
}
int main() {
while (cin >> N >> x) {
vec.clear();
for (int i = 0; i < N; ++i) {
int a; cin >> a;
vec.push_back(a);
}
cout << solve() << endl;
}
}
Submission Info
Submission Time |
|
Task |
B - Colorful Slimes |
User |
drken |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
3107 Byte |
Status |
AC |
Exec Time |
42 ms |
Memory |
640 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
400 / 400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
5 ms |
640 KB |
0_01.txt |
AC |
4 ms |
640 KB |
0_02.txt |
AC |
4 ms |
640 KB |
1_00.txt |
AC |
40 ms |
640 KB |
1_01.txt |
AC |
40 ms |
640 KB |
1_02.txt |
AC |
41 ms |
640 KB |
1_03.txt |
AC |
42 ms |
640 KB |
1_04.txt |
AC |
41 ms |
640 KB |
1_05.txt |
AC |
41 ms |
640 KB |
1_06.txt |
AC |
41 ms |
640 KB |
1_07.txt |
AC |
40 ms |
640 KB |
1_08.txt |
AC |
40 ms |
640 KB |
1_09.txt |
AC |
40 ms |
640 KB |
1_10.txt |
AC |
31 ms |
640 KB |
1_11.txt |
AC |
40 ms |
640 KB |
1_12.txt |
AC |
37 ms |
640 KB |
1_13.txt |
AC |
27 ms |
640 KB |
1_14.txt |
AC |
40 ms |
640 KB |
1_15.txt |
AC |
32 ms |
640 KB |
1_16.txt |
AC |
36 ms |
640 KB |
1_17.txt |
AC |
40 ms |
640 KB |