Hướng dẫn giải của Sơn tường
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; fo=''; maxn=1000010; var n,res,m:longint; re,mm,s:int64; a,st,pos,d,f:array[0..maxn] of longint; procedure doc; var i:longint; begin read(n,m); for i:=1 to n do begin read(a[i]); re:=re+a[i]; end; end; procedure timmin; var i,l,r:longint; begin st[0]:=-1; l:=1; r:=0; for i:=1 to n do begin while (a[i]<=st[r]) and (r>=l) do r:=r-1; r:=r+1; st[r]:=a[i]; pos[r]:=i; while i-pos[l]>m-1 do l:=l+1; d[i]:=st[l]; end; end; procedure tinh; var i,j:longint; begin mm:=m; res:=1; f[1]:=m; for i:=m+1 to n do begin j:=res-1; while (j>0) and (d[f[j+1]]<=d[i]) and (f[j]+m>=i) and (d[f[j]]>=d[f[j+1]]) do j:=j-1; res:=j+2; f[res]:=i; end; s:=mm*d[f[1]]; for i:=2 to res do begin s:=s+(f[i]-f[i-1])*d[f[i]]; j:=d[f[i]]-d[f[i-1]]; if j>0 then s:=s+(mm-f[i]+f[i-1])*j; end; writeln(re-s); writeln(res); end; begin assign(input,fi); reset(input); assign(output,fo); rewrite(output); doc; timmin; tinh; close(input); close(output); end.
Code mẫu của RR
#include <iostream> #include <algorithm> #define FOR(i,a,b) for(int i=a; i<=b; i++) #define FORD(i,a,b) for(int i=a; i>=b; i--) #define MAXN 1100111 using namespace std; int debug=0; //Buffer reading int INP,AM; #define BUFSIZE (1<<10) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ fread(BUF,1,BUFSIZE,stdin); \ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //Buffer reading int n,x,a[MAXN],l[MAXN],r[MAXN],last[MAXN],h[MAXN]; void input() { GN(n); GN(x); FOR(i,1,n) GN(a[i]); while (n%x) { n++; a[n]=0; } } void init() { FOR(i,0,n/x-1) { int u=i*x+1; l[u]=a[u]; u+=x-1; r[u]=a[u]; } FOR(i,1,n) if (!l[i]) l[i]=min(l[i-1],a[i]); FORD(i,n,1) if (!r[i]) r[i]=min(r[i+1],a[i]); if (debug) { FOR(i,1,n) cout<<l[i]<<" "; cout<<endl; FOR(i,1,n) cout<<r[i]<<" "; cout<<endl; } } void solve() { FOR(i,x,n) last[i]=min(l[i],r[i-x+1]); memset(l,-1,sizeof l); memset(r,-1,sizeof r); FOR(i,0,n/x-1) { int u=i*x+1; l[u]=last[u]; u+=x-1; r[u]=last[u]; } if (debug) { FOR(i,1,n) cout<<last[i]<<" "; cout<<endl; } FOR(i,1,n) if (l[i]==-1) l[i]=max(l[i-1],last[i]); FORD(i,n,1) if (r[i]==-1) r[i]=max(r[i+1],last[i]); long long res=0LL; FOR(i,1,n) h[i]=max(l[i+x-1],r[i]); if (debug) { cout<<endl; FOR(i,1,n) cout<<l[i]<<" "; cout<<endl; FOR(i,1,n) cout<<r[i]<<" "; cout<<endl; FOR(i,1,n) cout<<h[i]<<" "; cout<<endl; cout<<endl; } FOR(i,1,n) res+=a[i]-h[i]; cout<<res<<endl; int cnt=0,u=h[n],ok=n+1; FORD(i,n,1) if (a[i]) if (i<ok || h[i]!=u) { cnt++; u=h[i]; ok=i-x+1; } cout<<cnt; } int main() { input(); init(); solve(); return 0; }
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> #include <ctime> #include <deque> #include <bitset> #include <cctype> #include <utility> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(int i = 0; i < (n); ++i) #define Repd(i,n) for(int i = (n)-1; i >= 0; --i) #define For(i,a,b) for(int i = (a); i <= (b); ++i) #define Ford(i,a,b) for(int i = (a); i >= (b); --i) #define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) #define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0; int ptr = 0; char gc() { if (rsz <= 0) { ptr = 0; rsz = (int) fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; } void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); } int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; } template<class T> bool gi(T &v) { v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc(); while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true; } typedef pair<int, int> II; const ld PI = acos(-1.0); const ld eps = 1e-9; const int dr[] = { -1, 0, +1, 0, 1, 1, -1, -1 }; const int dc[] = { 0, +1, 0, -1, 1, -1, 1, -1 }; const int inf = (int) 1e9 + 5; const ll linf = (ll) 1e16 + 5; const int mod = (ll) (1e9 + 7 + eps); #define ok puts("ok") #define maxn 2000005 int n, a[maxn], l[maxn], r[maxn], c[maxn], m; ll res = 0, ret = 0; int main(){ // freopen("in.txt", "r", stdin); gi(n); gi(m); For(i, 1, n) gi(a[i]); a[0] = a[n + 1] = -1; c[0] = c[n + 1] = -1; For(i, 1, n){ l[i] = i; while(a[l[i] - 1] >= a[i]) l[i] = l[l[i] - 1]; } Ford(i, n, 1){ r[i] = i; while(a[r[i] + 1] >= a[i]) r[i] = r[r[i] + 1]; } int start = 1, u; For(i, 1, n){ if(r[i] - l[i] < m - 1 || start > i) continue; int finish = r[i]; u = i; while(u < r[i] && a[u + 1] == a[i]) u++; if(finish - u >= m) finish = u; For(j, start, finish){ res += a[j] - a[i]; c[j] = a[i]; } start = finish + 1; } int i, j; for(i = 1; i <= n; i = j){ for(j = i; j <= n && c[j] == c[i]; j++); ret += (j - i + m - 1) / m; } cout << res << endl << ret << endl; return 0; }
Bình luận