akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <functional>

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define INF (1<<29)

typedef pair<int, int> pii;

int N, K;
int c[5000], r[5000];
vector<int> road[5000];
vector<pii> g[5000]; // cost, to
bool done[5000];
int d[5000];

int main() {
	cin >> N >> K;
	REP(i, N) scanf("%d %d", &c[i], &r[i]);
	
	REP(i, K) {
		int a, b;
		scanf("%d %d", &a, &b);
		a--; b--;
		road[a].push_back(b);
		road[b].push_back(a);
	}
	
	REP(i, N) {
		int cost = c[i];
		int from = i;
		fill(done, done + N, false);
		
		queue<pii> que;
		que.push(pii(r[i], from));
		
		while (!que.empty()) {
			pii now = que.front(); que.pop();
			
			int lim = now.first;
			int pos = now.second;
			
			if (lim < 0 || done[pos]) continue;
			done[pos] = true;
			if (from != pos) g[from].push_back(pii(cost, pos));
			
			REP(j, road[pos].size()) que.push(pii(lim - 1, road[pos][j]));
		}
	}
	
	priority_queue<pii, vector<pii>, greater<pii> > pq; // cost, pos
	pq.push(pii(0, 0));
	fill(d, d + N, INF);
	
	while (!pq.empty()) {
		pii now = pq.top(); pq.pop();
		
		int nc = now.first;
		int pos = now.second;
		
		if (d[pos] <= nc) continue;
		d[pos] = nc;
		
		REP(i, g[pos].size()) {
			int cost = g[pos][i].first;
			int to = g[pos][i].second;
			
			if (d[to] > d[pos] + cost) pq.push(pii(d[pos] + cost, to));
		}
	}
	
	cout << d[N - 1] << endl;	
	return 0;
}

Measured memory_bytes: 192980
#include<cstdio>
#include<algorithm>
inline void read(int&r)
{
	register char c;r=0;
	do c=getchar();while(c<'0'||c>'9');
	do r=r*10+c-'0',c=getchar();while(c>='0'&&c<='9');
}

int a[200000];
bool b[200000];
int main()
{
	int n,i,j,x,s=0;read(n);
	for(i=0;i<n;i++)read(a[i]);
	std::sort(a,a+n);
	for(i=n;i--;)
		if(!b[i])
		{
			x=(1<<(32-__builtin_clz(a[i])))-a[i];
			j=std::lower_bound(a,a+n,x)-a;
			if(j<i&&a[j]==x&&!b[j])b[j]=true,s++,a[j]--;
		}
	printf("%d\n",s);
}

Measured memory_bytes: 1024
#include<iostream>
#include<cmath>
#include <iomanip>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;
using LL = long long;

LL a, b, n;

double aa, bb, nn;

LL res1, res2, res3;

int main() {

	cin >> a >> b >> n;

	if (b != 1) {
		if (n / b >= 1) {
			if (a <= b) {
				res1 = a - 1;
			}
			else {
				aa = a;
				bb = b;
				nn = n;
				for (double i = aa - 1; i >= 0; i--) {
					if (((bb / aa) * i <= floor((bb / aa) * i) && floor((bb / aa) * i) < (bb / aa) * (i + 1.0)) ||
						((bb / aa) * i <= ceil((bb / aa) * i) && ceil((bb / aa) * i) < (bb / aa) * (i + 1.0))) {
						res1 = i;
						break;
					}
				}
			}
		}
		else {
			if (a <= b)
				res1 = floor(n * a / b);
			else {
				aa = a;
				bb = b;
				nn = n;
				for (double i = floor(nn / bb * aa + 1) - 1; i >= 0; i--) {
					if (((bb / aa) * i <= floor((bb / aa) * i) && floor((bb / aa) * i) < (bb / aa) * (i + 1.0)) ||
						((bb / aa) * i <= ceil((bb / aa) * i) && ceil((bb / aa) * i) < (bb / aa) * (i + 1.0))) {
						res1 = i;
						break;
					}
				}
			}
		}
	}
	if (b == 1)res1 = 0;

	cout << res1 << endl;

	return 0;

}

Measured memory_bytes: 3736
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define MOD 1000000007
#define pb emplace_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(x) (ll)x.size()
#define F first
#define S second
#define FOR(i,a,b) for(ll i=a;i<=b;++i)
#define ROF(i,a,b) for(ll i=a;i>=b;--i)
typedef long long ll;
using namespace std;

int main(){
    IOS
    int k;
    cin >> k;
    ll sum = 0;
    FOR(i,1,k){
        FOR(j,1,k){
            FOR(l,1,k){
                sum += __gcd(__gcd(i,j),l);
            }
        }
    }
    cout << sum;
    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int n, h;
  cin >> n >> h;
  vector<int> a(n), b(n);
  rep(i, n) cin >> a[i] >> b[i];

  int max_a = *max_element(a.begin(), a.end());
  sort(b.begin(), b.end(), greater<int>());
  ll d = 0;
  int natk = 0;
  rep(i, n) {
    if (d >= h) {
      printf("%d\n", natk);
      return 0;
    }
    if (b[i] <= max_a) break;
    d += b[i];
    ++natk;
  }
  natk += (h - d + max_a - 1) / max_a;
  printf("%d\n", natk);
  return 0;
}

Measured memory_bytes: 4020
//A.cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
  int X,Y,Z;
  cin >> X >> Y >> Z;
  int Ans = X/(Y+Z);
  if(X%(Y+Z)==Z) printf("%d\n",Ans);
  else printf("%d\n",Ans - 1);
  return 0;

}


Measured memory_bytes: 256
#include <iostream>
#define REP(i,n) for (int i=0;i<(n);i++)
using namespace std;
int main()
{
    int n,v,input;
    long maxv = -10000000000;
    long minv = 10000000000;

    cin >> n;
    REP(i, n){
        cin >> input;
        if (maxv < input-minv)
            maxv = input-minv;
        if (minv > input)
            minv = input;
    }
    cout << maxv << endl;
    return 0;
}

Measured memory_bytes: 3088
#!/usr/bin/env python3
#!/usr/bin/env pypy3

import sys
sys.dont_write_bytecode = True
stdin = sys.stdin
input = stdin.readline
sys.setrecursionlimit(10000000)

#import numpy as np
#import scipy as sp

# Python 3 modules: https://docs.python.org/3/library/

import math, itertools, operator
from math import *
from math import factorial as fact
from operator import itemgetter, attrgetter
from itertools import permutations, combinations
from functools import reduce, lru_cache
# Use scipy for stats: https://docs.scipy.org/doc/scipy/reference/stats.html
# Before Python 3.5.  Import from math after it.
from fractions import gcd
from fractions import Fraction as Frac

inf = float('inf')

def lcm(a, b):
    return a * b // gcd(a,b)

def perm(a, b):
    import scipy.special
    return scipy.special.perm(a, b, exact = True)

def comb(a, b):
    import scipy.special
    return scipy.special.comb(a, b, exact = True)

def dfact(n):
    import scipy.special
    return scipy.special.factorial2(n, exact = True)

def prod(l):
    return reduce(operator.mul, l)

def input_ints(func = input, sep = None, conv = int):
    return list(map(conv, func().split(sep = sep)))

################################################################################


def main():
    A, B, C, D = list(map(int, input().split()))

    # // excludes 0
    s0 = (A-1) // C
    s1 = (B-0) // C
    t0 = (A-1) // D
    t1 = (B-0) // D
    u0 = (A-1) // lcm(C,D)
    u1 = (B-0) // lcm(C,D)
    s = s1 - s0
    t = t1 - t0
    u = u1 - u0
    c = s + t - u
    c = B - A + 1 - c
    print(c)


if __name__ == '__main__':
    main()


Measured memory_bytes: 5124
#include<bits/stdc++.h>
using namespace std;
 
#define DEBUG
 
typedef long long int ll;
typedef long double ld;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define MOD (ll)(1e9 + 7)
#define vi vector<int>
#define vii vector<vector<int> >
#define vl vector<ll>
#define vll vector<vector<ll> >
#define vc(T, nm) vector<T> nm
#define pb push_back
#define popb pop_back
#define si set<int>
#define sl set<ll>
#define F first
#define S second
#define pii pair<int, int>
#define mp make_pair
#define insert ins
#define ers erase
#define FORA(x, s, e, inc) for(ll x = s; x != e; x += inc)
#define ROFA(x, s, e, inc) for(ll x = s; x != e; x -= inc)
#define FOR(x, s, e) FORA(x, s, e, 1)
#define ROF(x, s, e) ROFA(x, s, e, 1)
#define loop(x, n) FOR(x, 0, n)
#define rd1(t, a) 					t a; cin >> a;
#define rd2(t, a, b) 				rd1(t, a); rd1(t, b); 
#define rd3(t, a, b, c) 			rd2(t, a, b); rd1(t, c);
#define rd4(t, a, b, c, d) 			rd3(t, a, b, c); rd1(t, d);
#define rd5(t, a, b, c, d, e) 		rd4(t, a, b, c, d); rd1(t, e);
#define rd6(t, a, b, c, d, e, f) 	rd5(t, a, b, c, d, e); rd1(t, f);
#define rdA(t, nm, len)				t nm[len]; loop(i, len) {cin >> nm[i];}
#ifdef DEBUG
	#define deb(v) cout << endl << #v << ": " << v << endl
	#define db1(v) cout << endl << #v << ": " << "[ "; for(auto x: v) {cout << x << " ";}; cout << "]" << endl;
	#define db2(v) cout << endl << #v << ": " << endl; for(auto r: v) {cout << "[ "; for(auto x: r) {cout << x << " ";}; cout << "]" << endl;};
	#define dbl cout << "-------------------------------" << endl
#else
	#define deb(v)
	#define db1(v)
	#define db2(v)
	#define dbl
#endif

int solve(vector<string> &A) {
	
	vc(float, f);
	
	FOR(i, 0, A.size()) {
		f.pb(stof(A[i]));
	}



	return 1;
}

int main() {
	
	fastio;
	
	// vc(string, s);
	// s.pb("0.6");
	// s.pb("0.7");
	// s.pb("0.8");
	// s.pb("1.2");
	// s.pb("0.4");
	
	// cout << solve(s);

	rd1(ll, n)
	rd1(string, s);

	bool flag = false;
	if(n % 2 == 0) {
		ll mid = n/2;
		// mid += 1;

		FOR(i, 0, mid) {
			if(s[i] == s[mid + i])
				flag = true;
			else {
				flag = false;
				break;
			}
		}
	}

	if(flag)
		cout << "Yes";
	else
		cout << "No";
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll gcd( ll x, ll y );
ll lcm( ll x, ll y );

int main()
{
    int n;
    int p[11111];
    int price = 0;

    scanf("%d", &n );

    for ( int i = 0; i < n; ++i ) {
        scanf("%d", &p[i] );
    }

    sort( p, p + n, greater<int>() );

    price = p[0] / 2;
    for ( int i = 1; i < n; ++i ) {
        price += p[i];
    }

    printf("%d\n", price );

    return 0;
}

ll gcd( ll x, ll y )
{
    if ( y == 0 ) return x;
    return gcd( y, x % y );
}

ll lcm( ll x, ll y )
{
    return x / gcd( x, y ) * y;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int A, B, C;
    cin >> A >> B >> C;

    cout << max(0, C - (A-B)) << endl;

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

long long int kotae(string s) {

  if (s.size() == 1) {
    return stoll(s);
  }

  long long int sum = stoll(s);
  for (int i = 1; i < s.size(); i++) {
    sum += kotae(s.substr(0, i)) + stoll(s.substr(i)) * pow(2, i - 1);
  }
  return sum;
}

int main() {
  string s;
  cin >> s;

  cout << kotae(s) << endl;
}


Measured memory_bytes: 512
def cc092():
    n = int(input())
    an = [0] + list(map(int, input().split())) + [0]

    c = 0
    p = 0
    for i in an:
        c += abs(p-i)
        p = i

    for i in range(1, n+1):
        cc = abs(an[i-1]-an[i+1]) - (abs(an[i-1]-an[i]) + abs(an[i]-an[i+1]))
        print(c+cc)

cc092()

Measured memory_bytes: 14048
import java.io.*;
 
class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        int i=1;
        while(true){
            int x=Integer.parseInt(br.readLine());
            if(x==0) break;
            sb.append("Case "+i+": "+x+"\n");
            i++;
            }
        System.out.print(sb);
    }
}

Measured memory_bytes: 31476
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define per(i,n) for (int i = (n)-1; i >=0; --i)
using namespace std;
using ll = long long;
using vi = vector<int>;
using vv = vector<vi>;

int main(){
    int w,h,n;
    cin>>w>>h>>n;
    
    int minx=0, maxx=w, miny=0, maxy=h;
    int x,y,a;
    
    rep(i,n){
        cin>>x>>y>>a;
        if(a==1)minx=max(minx,x);
        if(a==2)maxx=min(maxx,x);
        
        if(a==3)miny=max(miny,y);
        if(a==4)maxy=min(maxy,y);
    }
    if(maxx<minx || maxy<miny )cout << 0 <<endl;
    else cout << (maxx-minx)*(maxy-miny) << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  int N, M;
  cin >> N >> M;
  vector<ll> A(N);
  rep(i, N) cin >> A[i];
  priority_queue<ll> q;
  rep(i, N) q.push(A[i]);
  rep(i, M) {
    ll tmp = q.top();
    q.pop();
    q.push(tmp / 2);
  }
  ll ans = 0;
  rep(i, N) {
    ans += q.top();
    q.pop();
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2168
#include<bits/stdc++.h>
using namespace std;
int find(int x);
int same(int x,int y);
void unite(int x,int y);
int p[100009],q[100009];

int main(){
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>p[i];
    q[i]=i;
  }
  for(int i=0;i<m;i++){
    int x,y;
    cin>>x>>y;
    if(!same(x,y))unite(x,y);
  }
  int cnt=0;
  for(int i=1;i<=n;i++){
    if(same(p[i],i))cnt++;
  }
  cout<<cnt<<endl;
  return(0);
}

int find(int x){
  if(x==q[x])return x;
  return q[x]=find(q[x]);
}

int same(int x,int y){
  if(find(x)==find(y))return 1;
  else return 0;
}

void unite(int x,int y){
  x=find(x);
  y=find(y);
  q[x]=y;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>

inline int rd() {
  int x; scanf("%d", &x);
  return x;
}

const int N = 5050, P = 1e9 + 7;

int n, size[N];
long long way[N];
long long f[N][N], g[N];
std::vector<int> G[N];

void dfs(int x, int fa) {
  size[x] = 1;
  f[x][1] = 1;
  for (int y : G[x]) if (y != fa) {
    dfs(y, x);
    for (int i = 1; i <= size[x]; ++i)
      for (int j = 1; j <= size[y]; ++j)
        g[i + j] = (g[i + j] + f[x][i] * f[y][j]) % P;
    for (int i = 1; i <= size[x]; ++i)
      for (int j = 2; j <= size[y]; j += 2)
        g[i] = (g[i] + P - f[x][i] * f[y][j] % P * way[j] % P) % P;
    size[x] += size[y];
    for (int i = 1; i <= size[x]; ++i)
      f[x][i] = g[i], g[i] = 0;
  }
}

int main() {
  n = rd();
  way[2] = 1;
  for (int i = 4; i <= n; i += 2)
    way[i] = way[i - 2] * (i - 1) % P;
  for (int i = 1; i < n; ++i) {
    int x = rd(), y = rd();
    G[x].push_back(y);
    G[y].push_back(x);
  }
  dfs(1, 0);
  long long ans = 0;
  for (int i = 2; i <= n; i += 2)
    ans = (ans + f[1][i] * way[i]) % P;
  ans = (ans % P + P) % P;
  std::cout << ans << std::endl;
  return 0;
}


Measured memory_bytes: 92716
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
 int m,n;
 cin>>m>>n;
 
 int aum=0;
 for(int i=0;i<n;i++){int a1; cin>>a1;aum+=a1;}
m++;
 int ans=aum/m;
 if(aum%m!=0){ans++;}
 cout<<ans<<endl;
 
    return 0;
    
}


Measured memory_bytes: 3108
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<sstream>
#include<iomanip>
#include<limits>
#include<deque>
#include<map>
#include<list>
#include<set>
#include <unordered_set>
#include<vector>
#include<cmath>
#include<cstdio>
#include<memory>
#include<bitset>
#include<stack>
#include <functional>
#include <queue>
#include <regex>

using namespace std;

constexpr int MOD = 1000000007;
constexpr int INF = 1050000000;

#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl

#define Tof(x) (x) ? Yes : No
#define TOF(x) (x) ? YES : NO
#define tof(x) (x) ? yes : no

using ll = long long;


/*vectorの要素を全部確認するやつだよ。


for (vector<int>::iterator itr = ans.begin(); itr != ans.end(); ++itr) {
	cout << *itr << " ";
}


*/


/*for文でx,yを上下左右確認するやつだよ。

int dy[] = { 0, 1, 0, -1 };
int dx[] = { 1, 0, -1, 0 };


for (int i = 0; i < 4; i++) {
	int ny = y + dy[i];
	int nx = x + dx[i];
}
*/

/*繰り返し二乗法だよ。modもとってくれるよ。n^kをmodで割った余りでやってくれるよ。

ll POW_MOD(ll n, ll k, ll mod) {
	ll r = 1;

	for (; k > 0; k >>= 1) {
		if (k & 1) {
			r = (r * n) % mod;
		}
		n = (n * n) % mod;
	}
	return r;
}


*/

/*2重for文書くのめんどくなった時用だよ。

for (int i = 0; i < h; i++) {
	for (int j = 0; j < w; j++) {

	}
}

*/

int main(void) {
	int n; cin >> n;
	ll a[100000];

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	sort(a, a + n);

	ll ans = 1;

	for (int i = n - 1; i > 0; i--) {
		if (a[i] == a[i - 1]) {
			if (ans == 1) {
				ans *= a[i];
				i--;
			}
			else {
				ans *= a[i];
				cout<<ans<<endl;return 0;
			}
		}
	}

	cout << 0 << endl;


}


Measured memory_bytes: 1024
N, K=map(int, input().split())
V=list(map(int, input().split()))
NKmin=min(N, K)
out=0
for a in range(NKmin+1):
  for b in range(NKmin+1-a):
    zan=K-a-b
    if a==0 and b==0:
      continue
    elif b==0:
      tmp=V[:a]
    else:
      tmp=V[:a]+V[-b:]
    tmp.sort()
    s=sum(tmp)
    u=min(zan, len(tmp))
    for i in range(u):
      if tmp[i]<0:
        s+=-tmp[i]
      else:
        break
        
    if out<s:
      out=s
print(out)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <math.h>
#include<algorithm>
using namespace std;

int main(){
  string S;
  cin >> S;
  int ans;
  ans=0;
  for(int i=0;i<S.size();i++){
   if(S[i]=='+'){
    ans=ans+1; 
   }
    else{
     ans=ans-1; 
    }
  }
  cout << ans << endl;
return 0;}

Measured memory_bytes: 256
X, Y = list(map(int, input().split()))
if Y == 0:
  print(X)
else:
  P = list(map(int, input().split()))
  num = 0
  for i in range(Y + 1):
    num = X - i
    if num not in P:
      print(num)
      break
    num = X + i
    if num not in P:
      print(num)
      break


Measured memory_bytes: 9048
N, M, X = map(int, input().split())
C = []
L = []
for i in range(N):
    B = list(map(int, input().split()))
    C.append(B[0])
    L.append(B[1:])

res = 10 ** 9
for i in range(2 ** N):
    c = 0
    s = [0 for _ in range(M)]
    for j in range(N):
        if i >> j & 1:
            c += C[j]
            for k in range(M):
                s[k] += L[j][k]
    f = 1
    for j in range(M):
        if s[j] < X:
            f = 0
            break
    if f:
        res = min(res, c)

if res == 10 ** 9:
    print(-1)
else:
    print(res)


Measured memory_bytes: 68752
<?php

$input = trim(fgets(STDIN));
if ($input == 1) {
	echo 'Hello World';
	exit(0);
}

$count = 0;
$init = 0;
while (true) {
	$input = trim(fgets(STDIN));
	$input = explode(" ", $input);
	foreach ($input as $value) {
		$init += (int)$value;
		++$count;
	}
	if ($count >= 2) {
		break;
	}
}
echo $init;

Measured memory_bytes: 4856
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define ll long long
int main()
{
	std::ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//ll tt;	cin>>tt;	while(tt--)
	{
		ll n,i,sum;
		cin>>n;
			sum=0;
		for(i=1;i<=n;i++)
		{
			if(i%3!=0 and i%5!=0)	sum+=i;

		}
 			cout<<sum;
 	}
	cerr<<" Execution : "<<(1.0*clock())/CLOCKS_PER_SEC<<"s \n";
		
		
return 0;
}

Measured memory_bytes: 3792
#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(long long (i)=0;(i)<(n);(i)++)
#define reps(i,s,n) for(long long (i)=(s);(i)<(n);(i)++)
#define repr(i,n) for(int (i)=(n)-1;(i)>=0;(i)--)
#define all(v) (v).begin(),(v).end()
#define chmax(a, b) a = max((a),(b))
#define chmin(a, b) a = min((a),(b))
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define inf 1000000000
#define llinf 1000000000000000


typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;



int main(){
    int n,q,k;
    cin>>n>>k>>q;
    vint a(n);
    rep(i,n){
        a[i]=0;
    }
    rep(i,q){
        int b;
        cin>>b;
        a[b-1]++;
    }
    rep(i,n){
        if(a[i]>=q-k+1){
            cout<<"Yes"<<endl;
        }
        else{
            cout<<"No"<<endl;
        }
    }
}

Measured memory_bytes: 1024
#define LOCAL
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second	
#define db 0
#define EPS (1e-7)    //0.0000001 the value
#define PI (acos((ld)-1.0))
#define MAXN (300006)
#define ll long long int 
#define ld long double
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
#define FOR(ii, ss, ee) for(ll ii = ss; ii < (ll)ee; ++ii)
#define space " "
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define ph push
#define btinpct(x) __builtin_popcountll((x))
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
typedef pair <pi, pi> dpi;
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;}string to_string(bool b){return (b ? "true" : "false");}template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}template <typename A>string to_string(A v) {bool first = true;string res = "{";for (const auto &x : v) {if (!first) {res += ", ";}first = false;res += to_string(x);}res += "}";return res;}void degug_out() { cerr << endl; }template <typename Head, typename... Tail>void degug_out(Head H, Tail... T) {cerr << " " << to_string(H);degug_out(T...);}inline ll gcd(ll a,ll b){if(a>b)swap(a,b);if(a==0)return b;return gcd(b%a,a);}
#ifdef LOCAL
#define degug(...) cerr << "[" << #__VA_ARGS__ << "]:", degug_out(__VA_ARGS__)
#else
#define degug(...) 42
#define cerr if(0)cout
#endif
ll n,k;
int main()
{
	cin>>n>>k;
	if(k==1){cout<<0;return 0;}
	cout<<n-k<<'\n';
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 110
#define INF 0x3f3f3f3f
#define MST(vis,x) memset(vis,x,sizeof(vis))
map<string ,int>ma;
string s1[maxn];
int main()
{
    int n,m;
    while(scanf("%d",&n)!=EOF)
    {
        string temp;
        ma.clear();
        for(int a=1;a<=n;a++)
        {
            cin>>s1[a];
            ma[s1[a]]++;
        }
        scanf("%d",&m);
        for(int a=1;a<=m;a++)
        {
            cin >> temp;
            ma[temp]--;
        }
        int maxx=-INF;
        for(int a=1;a<=n;a++)
        {
            maxx=max(maxx,ma[s1[a]]);
        }
        if(maxx<0)maxx=0;
        printf("%d\n",maxx);
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;

#define rep(idx, N) for (u64 idx = 0; idx < N; idx++)

int main() {
  string s;
  cin >> s;

  u32 ans = 0;
  u32 r = 0;
  rep(i, 3) {
    if (s[i] == 'R') {
      r++;
    } else {
      if (r > ans)
        ans = r;
      r = 0;
    }
  }

  if (r > ans)
    ans = r;

  cout << ans;

  return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef complex<double> P;

void dfs(int v, int *used, vector< vector<int> > &G, vector<int> &vs){
  used[v] = true;
  REP(i, G[v].size()){
    int next = G[v][i];
    if(!used[next]) dfs(next, used, G, vs);
  }
  vs.push_back(v);
}

void rdfs(int v, int cnt, int *used, vector<int> &cmp, vector< vector<int> > &G){
  used[v] = true;
  cmp[v] = cnt;
  REP(i, G[v].size()){
    int next = G[v][i];
    if(!used[next]) rdfs(next, cnt, used, cmp, G);
  }
}

vector<int> scc(int V, vector< vector<int> > &G, vector< vector<int> > &RG){
  int used[V];
  memset(used, 0, sizeof(used));
  vector<int> vs, cmp(V);
  REP(i, V) if(!used[i]) dfs(i, used, G, vs);
  memset(used, 0, sizeof(used));
  int cnt = 0;
  REVERSE(vs);
  REP(i, vs.size()) if(!used[vs[i]]) rdfs(vs[i], cnt++, used, cmp, RG);
  return cmp;
}

int main() {
  int V, E; cin >>V >>E;
  vector< vector<int> > G(V), RG(V);
  REP(i, E){
    int f, t; cin >>f >>t;
    G[f].push_back(t);
    RG[t].push_back(f);
  }
  vector<int> cmp = scc(V, G, RG);
  int Q; cin >>Q;
  REP(q, Q){
    int a, b; cin >>a >>b;
    cout <<(cmp[a] == cmp[b]) <<endl;
  }
  return 0;
}

Measured memory_bytes: 3116
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	int N;
	cin >> N;
	int X;
	cin >> X;
	vector<int>v(N);
	for (int i = 0; i < N; i++)
	{
		cin >> v[i];
	}
	int saitei = 0;
	for (int i = 0; i < N; i++)
	{
		saitei += v[i];
	}
	sort(v.begin(),v.end());
	int nokori = X - saitei;
	int mizumasi = nokori / v[0];
	cout << N + mizumasi << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T> ostream& operator<<(ostream& s,const multiset<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1'000'000'007;
const ll inf=1'000'000'000'000'000'00;
const int INF=1'000'000'000;
const double EPS=1e-10;
const double PI=acos(-1);

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    int l,r,d;
    cin>>l>>r>>d;
    int ans=0;
    FOR(i,l,r+1){
        if(i%d==0) ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;

int main(){

	long long int n, ami, ama, mi, l, r, tmp;
	vector<int> v;
  
	cin>> n;
	v.resize(n);
	for(int i=0;i<n;i++) cin>> v[i];
  
  	if(v[n-1]!=2){
      	cout<< "-1" <<endl;
      	return 0;
    }
  
  	l=1;
  	r=1000000000000000000;
  	while(r-l>1){
      	mi=(l+r)/2;
      	tmp=mi;
      	for(int i=0;i<n;i++) tmp=tmp/v[i]*v[i];
      
      	if(3<tmp) r=mi;
      	else l=mi;
    }
  	ama=l;
  
  	l=1;
  	r=1000000000000000000;
  	while(r-l>1){
      	mi=(l+r)/2;
      	tmp=mi;
      	for(int i=0;i<n;i++) tmp=tmp/v[i]*v[i];
      
      	if(1<tmp) r=mi;
      	else l=mi;
    }
  	ami=r;
  
  	if(ama<ami) cout<< "-1" <<endl;
  	else cout<< ami << " " << ama <<endl;
  
  	return 0;
}

Measured memory_bytes: 768
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

int state[13];
int d[100001];
int go(int x){
    if(x==0) return 0;
    if(x==1 || x==6 || x==9) return 1;
    int &ans = d[x];
    if(ans!=-1)return ans;
    ans = 987654321;
    for(int i=0;i<=12;i++){
        if(x-state[i]>=0){
            ans = min(ans,go(x-state[i])+1);
        }
    }
    return ans;
}



int main(int argc, const char * argv[]) {
    
    int n;
    
    scanf("%d",&n);
    
    state[0] = 1;
    state[1] = 6;
    state[8] = 9;
    for(int i=2;i<=7;i++) state[i] = state[i-1]*6;
    for(int i=9;i<=12;i++) state[i] = state[i-1]*9;
    memset(d,-1,sizeof(d));
    printf("%d\n",go(n));
    return 0;
}


Measured memory_bytes: 3712
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int count = 0;
        for(int i = 1; i <= n; i++){
            if((1 <= i && i <= 9) || (100 <= i && i <= 999) || (10000 <= i && i <= 99999))  count++;
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define lint long long int 
using namespace std;

int main() {
	
        int n;
        cin>>n;
        int f=0;
        while(n--)
        {
                int startx=0,starty=0;
                int t=0;
                int x1,y1,t1;
                cin>>t1>>x1>>y1;
                int xx=abs(startx-x1);
                int yy=abs(starty-y1);
                
                int tt=abs(t-t1);
                int diff=tt-(xx+yy);
                if(diff%2==1|| diff<0)
                f=1;
                startx=x1;
                starty=y1;
                t=t1;
        }
        if(f==0)
        cout<<"Yes";
        else
        cout<<"No";
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const int MAXN = 100005;

int n,q,top;

ll S[MAXN];
ll cnt[MAXN];
ll ans[MAXN];

int main()
{
	scanf("%d%d",&n,&q);
	S[top = 1] = n;
	for (int i = 1;i <= q;i++)
	{
		ll a;
		scanf("%lld",&a);
		while (top >= 1 && S[top] >= a)
			top--;
		S[++top] = a;
	}
	if (top == 1)
	{
		int lim = S[1] % n;
		for (int i = 1;i <= n;i++)
			printf("%lld\n",S[1] / n + (i <= lim));
		return 0;
	}
	cnt[top] = 1;
	for (int i = top;i >= 2;i--)
	{
		ll cur = S[i];
		while (1)
		{
			int low = 1,high = i - 1;
			while (low < high)
			{
				int mid = low + high + 1 >> 1;
				if (S[mid] <= cur)
					low = mid;
				else
					high = mid - 1;
			}
			if (low == 1)
			{
				if (S[1] <= cur)
					ans[S[1]] += (cur / S[1]) * cnt[i];
				ans[cur % S[1]] += cnt[i];
				break;
			}
			cnt[low] += (cur / S[low]) * cnt[i];
			cur %= S[low];
		}
	}
	for (int i = S[1] - 1;i >= 1;i--)
		ans[i] += ans[i + 1];
	for (int i = 1;i <= n;i++)
		printf("%lld\n",ans[i]);
	return 0;
}

Measured memory_bytes: 4096
N,M = map(int,input().split())

d = {}
for i in range(M):
    p,y = map(int,input().split())
    if p in d.keys():
        d[p].append([p,y,i])
    else:
        d[p] = [[p,y,i]]

ans = []
for k in d.keys():
    d[k] = sorted(d[k],key=lambda x:x[1])
    for i,d_ in enumerate(d[k]):
        d_.append(i+1)
    ans += d[k]

ans = sorted(ans,key=lambda x:x[2])
for a in ans:
    print(str(a[0]).zfill(6)+str(a[3]).zfill(6))

Measured memory_bytes: 47660
#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  int a[n], b[n], c[n];
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < n; i++) cin >> b[i];
  for(int i = 0; i < n; i++) cin >> c[i];
  int d = -1;
  int ans = 0;
  for(int i = 0; i < n; i++){
    ans += b[a[i]-1];
    if(d+1 == a[i]) ans += c[d-1];
    d = a[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main{
	static int n, k;
	static int[] a;

	public static void main(String[] args){
		//入力
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		k = sc.nextInt();
		a = new int[n];
		for(int i = 0; i < n; i++){
			a[i] = sc.nextInt();
		}
		sc.close();

		//処理
		Arrays.sort(a);
		int ret = binarySearch();
		int ans = 0;
		if(ret >= 0){
			ans = Math.min(n, ret + 1);
		}

		//出力
		PrintWriter out = new PrintWriter(System.out);
		out.println(ans);
		out.flush();
	}

	private static int binarySearch(){
		int ng = n; //条件を満たさない
		int ok = -1;  //条件を満たす

		while(Math.abs(ok - ng) > 1){
			int mid = (ok+ng) / 2;
			if(isOK(mid)) ok = mid;
			else ng = mid;
		}

		return ok;
	}

	static int[][] dp = new int[5010][5010];

	private static boolean isOK(int notuse){
		int kp = k - a[notuse];
		if(kp < 0) return false;
		
		for(int[] t : dp) Arrays.fill(t, -1);
		dp[0][0] = 1;
		List<Integer> b = new ArrayList<>();
		for(int i = 0; i < n; i++){
			if(i != notuse && a[i] < k) b.add(a[i]);
		}
		int m = b.size();

		for(int i = 0; i < m; i++){
			for(int j = 0; j < k; j++){
				if(dp[i][j] == 1){
					dp[i+1][j] = 1;
					if(j + b.get(i) < k) dp[i+1][j+b.get(i)] = 1;
				}
			}
		}

		boolean f = true;
		for(int i = kp; i < k; i++){
			if(dp[m][i] == 1) f = false;
		}

		return f;
	}
}

Measured memory_bytes: 169152
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> A(N), B(N);
	for (int i = 0; i < N; ++i) cin >> A[i];
	for (int i = 0; i < N; ++i) cin >> B[i];
	long long sum = 0;
	for (int i = 0; i < N; ++i) {
		sum += A[i] - B[i];
	}
	if (sum < 0) {
		cout << -1 << endl;
	}
	else {
		vector<int> keyence;
		for (int i = 0; i < N; ++i) {
			if (A[i] >= B[i]) {
				keyence.push_back(A[i] - B[i]);
			}
		}
		sort(keyence.begin(), keyence.end());
		int ans = keyence.size();
		for (int i = 0; i < keyence.size(); ++i) {
			if (sum < keyence[i]) {
				ans = i;
				break;
			}
			sum -= keyence[i];
		}
		cout << N - ans << endl;
	}
	return 0;
}

Measured memory_bytes: 2040
// #pragma GCC target("avx2")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
long long fact[C_SIZE];
long long finv[C_SIZE];
long long inv[C_SIZE];
long long Comb(int a,int b){
 	if(a<b||b<0)return 0;
 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
}
void init_C(int n){
	fact[0]=finv[0]=inv[1]=1;
	for(int i=2;i<n;i++){
		inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	}
	for(int i=1;i<n;i++){
		fact[i]=fact[i-1]*i%mod;
		finv[i]=finv[i-1]*inv[i]%mod;
	}
}
long long pw(long long a,long long b){
	if(a<0LL)return 0;
	if(b<0LL)return 0;
	long long ret=1;
	while(b){
		if(b%2)ret=ret*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return ret;
}
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
double ABS(double a){return max(a,-a);}
int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
// ここから編集しろ
char in[110];
int main(){
	int a;scanf("%d%s",&a,in);
	if(a<3200)printf("red\n");
	else printf("%s\n",in);
}

Measured memory_bytes: 128
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pill pair<ll,ll>
#define f first
#define s second
#define speed ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const ll N = 2e5 + 1;
ll n,m;
vector<ll> g[N];
ll dp[N];
bool ch[N];
ll dfs(ll v){
	if(ch[v])return dp[v];
	ch[v] = 1;
	for(int i = 0 ; i < g[v].size() ; i++){
		dp[v] = max(dp[v],dfs(g[v][i]) + 1);
	}
	return dp[v];
}

int main() {
	speed;
	cin >> n >> m;
	while(m--){
		ll x,y;
		cin >> x >> y;
		g[x].pb(y);
	}
	ll ans = 0;
	for(int i = 1; i <= n ; i++){
		if(!ch[i])ans = max(ans,dfs(i));
	}
	cout << ans;
}
/*
Timus : 288471KD
Atcoder : Zhabka
Codeforces : Zhabka
mail : dzhon.snoudin@mail.ru
*/



Measured memory_bytes: 10496
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <bitset>
#include <limits>
#include <iomanip>
using namespace std;
using ll = long long;
constexpr ll INF = 1010000000000000017LL;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define all(v) v.begin(), v.end()

ll GCD(ll a, ll b) { if(b==0) return a; else return GCD(b, a%b); }
ll LCM(ll a, ll b) { return a/GCD(a,b)*b; }

class APayment {
public:
	void solve(std::istream& in, std::ostream& out) {
        int n;in>>n;
        if(n%1000==0) out<<0<<endl;
        else out<<1000+1000*(n/1000)-n<<endl;
	}
};


int main() {
	APayment solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3212
// aribon4-4_b
// CODE FESTIVAL 2016 Tournament Round 3 A ストラックアウト
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    int N, M, K;
    cin >> N >> M >> K;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];

    vector<vector<ll>> dp(K+1, vector<ll>(N, -1));
    dp[0].assign(N, 0);

    vector<deque<ll>> deqs(K+1);
    deqs[0].emplace_back(0);

    REP(i, N){

        REPN_REV(k, 1, K+1) {

            if (deqs[k-1].empty()) continue;

            // スライド最大値
            dp[k][i] = dp[k-1][deqs[k-1].front()] + k * A[i];

            // deque更新
            while (not deqs[k].empty() && dp[k][deqs[k].back()] <= dp[k][i]){
                deqs[k].pop_back();
            }
            deqs[k].emplace_back(i);

            // 先頭からpop
            if (deqs[k].front() == i - M){
                deqs[k].pop_front();
            }
        }

    }

//    REP(k, K+1) { print(k, dp[k]); }

    ll ans = 0;
    REP(i, N){
        ans = max(ans, dp[K][i]);
    }
    print(ans);


    return 0;
}


Measured memory_bytes: 237824
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const long long INF = 1LL << 60;

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i=0; i<N; i++) cin >> A[i];
    ll min_cost = INF;

    for(int i=-100; i<=100; i++) {
        ll cost=0;
        for(int j=0; j<N; j++) {
            cost += pow((A[j]-i), 2);
        }
        min_cost = min(cost, min_cost);
    }
    cout << min_cost << endl;
}

Measured memory_bytes: 3604
#include <cstdio>

int n ,A[50];

//从输入值M中减去所选元素的递归函数
int solve (int i, int m){
    if (m == 0) return 1;//检查ｍ=0时返回true
    if (i >= n) return 0;//超过数组范围，返回false
    int res = solve(i + 1, m) || solve(i + 1,m-A[i]);//检查数组本身有无m或任意相加是否为m
    return res;                                                                                                 
}


int main(){
    int q,M,i;

    scanf("%d",&n);
    for(i=0; i<n; i++) scanf("%d", &A[i]);
    scanf("%d", &q);
    for(i=0; i<q; i++){
        scanf("%d", &M);
        if(solve(0,M)) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}


Measured memory_bytes: 2608
#include <bits/stdc++.h>
using namespace std;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
const int INF = 1 << 30;

class Solver {
  public:
    bool solve() {
        int N; cin >> N;
        vector<int> index_w(N + 1, -1), index_b(N + 1, -1);
        vector<vector<int>> sum_w(N * 2 + 1, vector<int>(N + 2));
        vector<vector<int>> sum_b = sum_w;

        rep(i, N * 2) {
            char c;
            int a;
            cin >> c >> a;
            (c == 'B' ? sum_b : sum_w)[i][a]++;
            (c == 'B' ? index_b : index_w)[a] = i;
        }
        rep(i, N * 2) rep(j, N + 2) {
            sum_b[i + 1][j] += sum_b[i][j];
            sum_w[i + 1][j] += sum_w[i][j];
        }
        rep(i, N * 2 + 1) for(int j = N; j > 0; j--) {
            sum_b[i][j - 1] += sum_b[i][j];
            sum_w[i][j - 1] += sum_w[i][j];
        }
        // debug(sum_b);
        // debug(sum_w);

        vector<vector<int>> dp(N + 1, vector<int>(N + 1, INF));
        dp[0][0] = 0;
        rep(i, N + 1) {
            rep(j, N + 1) {
                if(i == 0 and j == 0) continue;
                int a = i == 0 ? INF : (dp[i - 1][j] + sum_b[index_b[i]][i + 1] + sum_w[index_b[i]][j + 1]);
                int b = j == 0 ? INF : (dp[i][j - 1] + sum_b[index_w[j]][i + 1] + sum_w[index_w[j]][j + 1]);
                dp[i][j] = min(a , b);
            }
        }
        // debug(dp);
        cout << dp[N][N] << endl;
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}


Measured memory_bytes: 78848
#include<bits/stdc++.h>
#define ll long long int
#define mk make_pair
#define pb push_back
#define INF (ll)1e12
#define pii pair<ll,ll>

#define f(i,a,b) for(ll i=a;i<b;i++)
#define fb(i,a,b) for(ll i=a;i>b;i--)
#define ff first
#define ss second
#define PI 3.141592653589793238
#define pq priority_queue<ll>
#define pqr priority_queue<ll,vector<ll>,greater<ll>()>
using namespace std;
ll pow_mod(ll a,ll b,ll mod)
{
	ll res=1;
	while(b!=0)
	{
		if(b&1)
		{
			res=(res*a)%mod;
		}
		a=(a*a)%mod;
		b/=2;
	}
	return res;
}
void solve()
{
    ll k;
    cin>>k;
    
    ll ans=-1;
    
    
    if(k%7==0)
    k/=7;
    
    k*=9;
    
    ans=-1;
    ll res=10;
    
    for(ll i=1;i<=k;i++){
        res%=k;
        
        if(res==1){
            ans=i;
            break;
        }
        
        res=(res*10)%k;
    }
    cout<<ans<<endl;
}
int32_t main()
{    ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     cout.tie(NULL);
     
//Start from Here.

  ll t;
  t=1;
 // cin>>t;
  while(t--)
  solve();
  
//Good Bye!
    return 0;
}

Measured memory_bytes: 3644
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int Sum(long long n) 
{
	int res = 0;
	while (n > 0) 
	{
		res += n % 10;
		n /= 10;
	}
	return res;
}
int main() 
{
	long long n, temp;
	cin >> n;
	int ans = Sum(n);
	temp = n;
	long long cnt = 1;
	while (temp >= 10) 
	{
		temp /= 10;
		cnt *= 10;
	}
	ans = max(ans, Sum(n / cnt * cnt - 1));
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define INCANT cin.tie(0), ios::sync_with_stdio(false), cout << fixed << setprecision(20)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define all(x) (x).begin(),(x).end()
#define out(a) cout << a << endl
#define PRINT(V) for (auto v : (V)) cout << v << " "

const int MOD = 1000000007;
const double PI = acos(-1.0);

void solve() {
    ll K, N;
    cin >> K >> N;
    vector<ll> A(N), B(N);
    rep(i, N) cin >> A.at(i);
    rep(i, N-1) B.at(i) = A.at(i+1)-A.at(i);
    B.at(N-1) = A.at(0) + K-A.at(N-1);
    int max_value = *max_element(all(B));
    out(K-max_value);
}
int main() {
    INCANT;
    solve();
    return 0;
}




Measured memory_bytes: 3456
n,t=gets.split.map &:to_i
a=gets.split.map &:to_i
max=[]
m=0
(n-1).downto(0) do |i|
  if a[i]>m
    m=a[i]
  end
  max<< m
end
max=max.reverse
diff=[]
(n-1).times do |i|
  diff<< a[i]-max[i+1]
end
g=diff.min
p diff.count{|i|i==g}

Measured memory_bytes: 10892
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	string s, t;
	cin >> n >> s >> t;
	
	int m = 0;
	for (int i = 1; i <= n; i++) {
		int cnt = 0;
		for (int j = 0; j < i; j++) {
			if (s[n - i + j] == t[j]) cnt++;
		}
		m = max(m, cnt);
	}

	cout << s.size() + t.size() - m << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define endl "\n"
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
	int n;
  	cin >> n;
  	cout << "ABC" << n << endl;
    return 0;
}


Measured memory_bytes: 3636
x, y = map(int, input().split())
if x in [1, 3, 5, 7, 8, 10, 12] and y in [1, 3, 5, 7, 8, 10, 12]:
  print('Yes')
elif x in [4, 6, 9, 11] and y in [4, 6, 9, 11]:
  print('Yes')
elif x == 2 and y == 2:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 61648
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;

map<string, ll> cnt;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("INP.txt", "r", stdin);
	//freopen("OUT.txt", "w", stdout);
	ll n;
	cin >> n;
	for (ll i = 0; i < n; i++) {
		string s;
		cin >> s;
		sort(s.begin(), s.end());
		cnt[s]++;
	}
	ll res = 0;
	for (map<string, ll>::iterator i = cnt.begin(); i != cnt.end(); i++) {
		ll val = (*i).second;
		res += ((val - 1) * val) / 2;
	}
	cout << res << '\n';
	return 0;
}	

Measured memory_bytes: 11264
#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MP make_pair
#define ll long long
#define fi first
#define se second
using namespace std;

template <typename T>
void read(T &x) {
    x = 0; bool f = 0;
    char c = getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
    for (;isdigit(c);c=getchar()) x=x*10+(c^48);
    if (f) x=-x;
}

template <typename T>
inline void Mx(T &x, T y) { x < y && (x = y); }

template <typename T>
inline void Mn(T &x, T y) { x > y && (x = y); }

const int P = 1e9+7;
const ll INF = 1e18;
ll fib[105], l;
ll m, T, n;


vector<pair<ll, ll> > res[100];
int main() {
	for (fib[0] = fib[1] = l = 1; fib[l] <= INF; l++)
		fib[l+1] = fib[l] + fib[l-1];
		
	res[1].push_back(MP(1, 2));
	res[1].push_back(MP(1, 3));
	res[1].push_back(MP(1, 4));
	for (int i = 1;i < l - 2; i++) {
		for (auto j: res[i]) {
			ll x = j.fi, y = j.se;
			x += y;
			while (x <= fib[i+3] + fib[i]) {
				res[i+1].push_back(MP(y, x));
				x += y;
			}
		}
	}
	
	for (read(T); T; T--) {
		read(n), read(m);
		n > m && (swap(n, m), 0);
		int k = 1;
		while (fib[k+1] <= n && fib[k+2] <= m) ++k;
		printf ("%d ", k);
		if (k == 1) {
			printf ("%lld\n", n * m % P);
			continue;
		}
		ll ans = 0;
		for (auto j: res[k-1]) {
			ll x = j.fi, y = j.se;
			if (y <= n) ans += (m - x) / y;
			if (y <= m) ans += (n - x) / y;
			ans %= P;
		}
		printf ("%lld\n", ans);
	}
	return 0;
}

Measured memory_bytes: 4096
#include <cstdio>
#include <math.h>

using namespace std;

int main() {
    double r;
    scanf("%lf", &r);

    double area = r * r * M_PI;
    double circumference = 2.0 * r * M_PI;

    printf("%lf %lf", area, circumference);
    return 0;
}



Measured memory_bytes: 2748
def c_peaks():
    N, M = [int(i) for i in input().split()]
    H = [int(i) for i in input().split()]
    Roads = [[int(i) for i in input().split()] for j in range(M)]

    height_max = [0] * N
    for a, b in Roads:
        height_max[a - 1] = max(height_max[a - 1], H[b - 1])
        height_max[b - 1] = max(height_max[b - 1], H[a - 1])

    return sum([1 for h, m in zip(H, height_max) if h > m])

print(c_peaks())

Measured memory_bytes: 30748