akhauriyash/Code-Regression huggingface dataset:
import Control.Applicative
import Control.Monad
import Data.List

main :: IO ()
main = do
  getLine
  [a, d] <- f
  m <- readLn
  solve a d <$> (reverse <$> replicateM m f) <*> readLn >>= print
  where
    f = map read <$> words <$> getLine

solve :: Int -> Int -> [[Int]] -> Int -> Int
solve a d xs k = a + (ok-1) * d
  where ok = foldl' f k xs
        f i [x, y, z]
          | x == 0 && y == i = z
          | x == 0 && z == i = y
          | x == 1 && y == i = z
          | otherwise = i



Measured memory_bytes: 3860
#include<stdio.h>
#include<string.h>
int main()
{
	char a[11],b[11],c[11];
	int n=0;
	scanf("%s",a);
	scanf("%s",b);
	scanf("%s",c);
	if(a[strlen(a)-1]==b[0]&&b[strlen(b)-1]==c[0])  printf("YES");
	else printf("NO");
	return 0;
}

Measured memory_bytes: 128
while True:
  n = int(input())
  if n == 0:
    break
  seq = []
  for _ in range(n):
    seq.append(int(input()))
  p_sum = -2000000
  for i in range(n):
    t_sum = 0
    for j in range(i,n):
      t_sum += seq[j]
      if t_sum > p_sum:
        p_sum = t_sum
  print(p_sum)


Measured memory_bytes: 5632
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define irep(i,a,b) for(ll i=ll(a);i>=ll(b);i--)
using ll = long long;
using namespace std;

int main(){
	ll a,b;
	cin>>a>>b;
	bool p=false;
	ll st=0;
	rep(i,0,max(a,b)+1){
		if(abs(a-i)==abs(b-i)){p=true;st=i;break;}
	}
	if(p) cout<<st;
	else cout<<"IMPOSSIBLE";
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<(a+n);i++)
#define var auto
using namespace std;
using ll = long long;

int main() {
  string s;
  cin >> s;
  if (s == "AAA" || s == "BBB") {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }

  return 0;
}


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

using namespace std;

const int maxn = 1e5+10;

int num[maxn], dp[maxn];

int main(void)
{
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> num[i];

	dp[2] = abs(num[2]-num[1]);

	for (int i = 3; i <= n; i++)
		dp[i] = min(dp[i-1]+abs(num[i]-num[i-1]), dp[i-2]+abs(num[i]-num[i-2]));

	cout << dp[n] << "\n";
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

int main(int, char**) {
  string s, t;
  cin >> s >> t;
  int a, b;
  cin >> a >> b;
  string u;
  cin >> u;
  if (s == u)
    --a;
  if (t == u)
    --b;
  cout << a << " " << b;

  return 0;
}

Measured memory_bytes: 888
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String S = scanner.next();
		String T = scanner.next();
		String judge = "No";
 
		int l = S.length();
 
		for (int i = 0; i < l; i++) {
			String end = S.substring(l-1,l);
			S = S.substring(0,l-1);
			S = end + S;
			if (T.equals(S)) {
				judge = "Yes";
				break;
			}
		}
		System.out.println(judge);
	}
}


Measured memory_bytes: 23252
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#include <functional>
#include <vector>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
const int inf=0x3f3f3f3f;
const int MOD=10007;

int main()
{
    char s[maxn];
    scanf("%s",s);
    int len=strlen(s);
    int maxx=0;
    int tot=0;
    for(int i=0;i<len;i++)
    {
        if(s[i]=='R')
        {
            tot++;
        }
        else
        {
            maxx=max(maxx,tot);
            tot=0;
        }
    }
    maxx=max(maxx,tot);
    tot=0;
    printf("%d\n",maxx);
}


Measured memory_bytes: 3828
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<long long,long long> ii; 	
typedef complex<long double> com;

const ll mod = 1e9+7;

ll n,m,s;
ii graph1[51][51];

vector <vector<ii>> graph;
vector <ll> dist;
vector <ii> tran;
vector <bool> visited;

struct node{
    ll w,p;
    bool operator<(const node& rhs) const{
        return w > rhs.w;
    }
};

ll get_id(ll i,ll j){
    return i*3000+j;
}

void dijkstra(ll u){
    dist[u] = 0;
    priority_queue<node> que;
    visited[u] = true;
    for (ii v : graph[u]){
        node temp;
        temp.p = v.first;
        temp.w = v.second;
        dist[v.first] = v.second;
        que.push(temp);
    }
    while (!que.empty()){
        node temp = que.top();
        que.pop();
        ll u = temp.p;
        ll w = temp.w;
        if (visited[u]) continue;
        visited[u] = true;
        for (ii v : graph[u]){
            if (visited[v.first]) continue;
            if (w + v.second < dist[v.first]){
                dist[v.first] = w + v.second;
                node t;
                t.p = v.first;
                t.w = dist[v.first];
                que.push(t);
            }
        }
    }
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> n >> m >> s;
    for (int z=0;z<m;z++){
        ll u,v,a,b;
        cin >> u >> v >> a >> b;
        u--;v--;
        graph1[u][v] = {a,b};
        graph1[v][u] = {a,b};
    }
    tran.resize(n);
    for (int z=0;z<n;z++){
        cin >> tran[z].fi >> tran[z].se;
    }
    graph.resize(n*3000);
    dist.resize(graph.size(),LLONG_MAX);
    visited.resize(graph.size(),false);
    for (int z=0;z<n;z++){
        for (int x=0;x+tran[z].first<3000;x++){
            graph[get_id(z,x)].push_back({get_id(z,x+tran[z].first),tran[z].second});
        }
    }
    for (int z=0;z<n;z++){
        for (int x=z+1;x<n;x++){
            if (graph1[z][x].first == 0) continue;
            if (graph1[z][x].second == 0) continue;
            for (int y=graph1[z][x].first;y<3000;y++){
                graph[get_id(x,y)].push_back({get_id(z,y-graph1[z][x].first),graph1[z][x].second});
                graph[get_id(z,y)].push_back({get_id(x,y-graph1[z][x].first),graph1[z][x].second});
            }
        }
    }
    dijkstra(min(s,ll(2999)));
    for (int z=1;z<n;z++){
        ll mini = LLONG_MAX;
        for (int x=0;x<3000;x++){
            mini = min(dist[get_id(z,x)],mini);
        } 
        cout << mini << endl;
    }
}

Measured memory_bytes: 28280
n,W=map(int,input().split())
items=[tuple(map(int,input().split())) for i in range(n)]
from collections import defaultdict
dp=defaultdict(int)
dp[0]=0
for w,v in items:
  for tw,tv in list(dp.items()):
    if tw+w<=W:
      dp[tw+w]=max(tv+v,dp[tw+w])
print(max(dp.values()))

Measured memory_bytes: 3944
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

/*
template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}*/


#define ARRAY_MAX 100005
const ll INF = 1e9 + 7;


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

const ll MOD = 1e9 + 7;


int main() {

	ll n, k;
	cin >> n >> k;

	if (k == 0)
	{
		cout << n * n << endl;
		return 0;
	}

	ll ans = 0;
	for (ll i = k + 1; i <= n; i++)
	{
		ll tmp = (n + 1) / i;
		ans += (i - k) * tmp;
		ans += max(0LL, (n + 1) % i - k);

	}
	
	cout << ans << endl;

	return 0;
}


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



int main(){
	while(true){
		int n,ans=0,k;
		char m;
		cin>>n;
		if(n==0){
			break;
		}
		int  dp[n+1][n+1]={};
		
		
		
		
		for(int p=1;p<=n;p++){
			for(int q=1;q<=n;q++){
				cin>>m;
				if(m=='.'){
					k=dp[p][q-1];
					if(k>dp[p-1][q]){
						k=dp[p-1][q];
					}
					if(k>dp[p-1][q-1]){
						k=dp[p-1][q-1];
					}
					k++;
					dp[p][q]=k;
					if(k>ans){
						ans=k;
					}
				}else{
					dp[p][q]=0;
				}
			}
		}

		//for(int p=0;p<=n;p++){
		//	for(int q=0;q<=n;q++){
		//		printf("(%2d)",dp[p][q]);
		//	}
		//	puts("");
		//}
		
		cout<<ans<<endl;
	}
}


Measured memory_bytes: 7028
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))


int main(void){
	vector<int> inp;
	int a;
	int ans = 0;
	int mi = 10;
	rep(i,5){
		cin >> a;
		inp.push_back(a);
		ans += a/10*10 + (a%10==0?0:10);
		chmin(mi,(a%10==0?10:a%10));
	}
	ans -= 10 - mi;
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 256
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
n = int(input())
print(a[n-1])


Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb(in,tmp) in.push_back(tmp)
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
using namespace std;
bool sc(string num,string in){
  bool han=true;
  rep(i,8){
    if(num[i]=='*')continue;
    if(num[i]!=in[i])han=false;
  }
  return han;
}

int main(){
  int n,m;
  while(cin>>n>>m,n||m){
    vector<string>num(n);
    vector<int>money(n);
    rep(i,n){
      cin>>num[i]>>money[i];
    }
    int sum=0;
    rep(i,m){
      string in;
      cin>>in;
      rep(j,n)
	if(sc(num[j],in))sum+=money[j];
    }
    cout<<sum<<endl;			 
  }

}

Measured memory_bytes: 1216
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define rep(i,n) for(int i = 0; i < (n); i++)
#define ENDL '\n'
#define print(i) std::cout << (i) << '\n'

#define int long long // at least int64 > 9*10^18
#define all(v) (v).begin(), (v).end()
/* libraries */

struct UnionFind
{
  int n;
  std::vector<int> par,size;
  UnionFind(int sz) : n(sz), par(sz,0), size(sz,1) {
    std::iota(par.begin(),par.end(),0);
  }
  int find(int x) {
    if(par[x]==x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x=find(x);y=find(y);
    if(x==y) return;
    if(size[x]<size[y]) std::swap(x,y);
    size[x]+=size[y];
    par[y]=x;
  }
};

struct Edge
{
	int a,b,c;
	Edge(int a,int b, int c) : a(a), b(b), c(c) {}
};

int kruskal(int n,std::vector<Edge>&edges) {
	std::sort(edges.begin(), edges.end(), [] (Edge a, Edge b) { return a.c < b.c; } );
	UnionFind uf(n);
	std::vector<Edge> min_tree;
	int cost = 0;
	for(Edge e:edges) {
		if(uf.find(e.a)==uf.find(e.b)) continue;
		cost += e.c;
		uf.unite(e.a,e.b);
	}
	return cost;
}

template <typename T>
std::vector<int> sort_indexes(const std::vector<T> &v) {
  std::vector<int> idx(v.size());
  std::iota(idx.begin(), idx.end(), 0);
  std::sort(idx.begin(), idx.end(), [&v](int i1, int i2) {return v[i1] < v[i2];});
  return idx;
}


signed main() {
	int n;
	std::cin >> n;
	std::vector<int> x(n);
	std::vector<int> y(n);
	rep(i,n) {
		int a,b;
		std::cin >> a >> b;
		x[i] = a;
		y[i] = b;
	}
	std::vector<Edge> edges;
	auto idx = sort_indexes(x);
	rep(i,n-1) {
		int f = x[idx[i]];
		int s = x[idx[i+1]];
		int dist = s-f;
		edges.emplace_back(idx[i],idx[i+1],dist);
	}
	auto idy = sort_indexes(y);
	rep(i,n-1) {
		int f = y[idy[i]];
		int s = y[idy[i+1]];
		int dist = s-f;
		edges.emplace_back(idy[i],idy[i+1],dist);
	}
	print(kruskal(n,edges));
	return 0;
}


Measured memory_bytes: 11504
n=int(input())
a=list(map(int,input().split()))
a=sorted(a,reverse=True)
comb_n=a[0]
a=a[1:]
r_ind=int(comb_n/2)

ans=0
for i in range(len(a)-1):
     if abs(a[i]-r_ind)<=abs(a[i+1]-r_ind):
          ans=a[i]
          break
print(comb_n,ans)

Measured memory_bytes: 14060
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;

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

	int n, d, x;
	cin >> n >> d >> x;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		x += (d + a - 1) / a;
	}
	cout << x << endl;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

template<class T> void gc(T &x)
{
    char c;
    int s = 0;
    x = 0;

    c = getchar_unlocked();

    if (c == '-') s = 1;
    else if ('0' <= c && c <= '9')  x = c - '0';

    while (true)
    {
        c = getchar_unlocked();

        if (c < '0' || c > '9') break;
        x = x * 10 + (c - '0');
    }

    if (s) x = -x;
}

int main()
{
    int N, H;

    gc(N);
    gc(H);

    vector<int> vA(N, 0);
    vector<int> vB(N, 0);

    for (int i = 0; i < N; i++)
    {
        gc(vA[i]);
        gc(vB[i]);
    }

    int mx = *max_element(vA.begin(), vA.end());

    sort(vB.begin(), vB.end());
    reverse(vB.begin(), vB.end());

    int ans = H;

    for (int i = 0; i <= N; i++)
    {
        // 振るだけの場合 0
        if (0 < i) H -= vB[i - 1];

        // 振る回数
        int cnt = 0;

        // 切り上げ
        if (0 < H) cnt = (H + mx - 1) / mx;

        // 最小攻撃回数を取得
        ans = min(ans, i + cnt);
    }

    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9+100;
const ll MOD = 1e9+7;
const bool debug = 0;
//-----------------------------------------------//

int main() {
	string n;
	cin >> n;
	REP(i, n.size()) n[i] -= '0';
	
	REP(i, 1<<3) {
		int cur = n[0];
		REP(j, 3) {
			if (i >> j & 1) cur += n[j + 1];
			else cur -= n[j + 1];
		}
		if (cur == 7) {
			printf("%d", n[0]);
			REP(j, 3) printf("%c%d", i >> j & 1 ? '+' : '-', n[j + 1]);
			puts("=7");
			break;
		}
	}
	
	return 0;
}


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

const int INF = 1e9;

struct UnionFind {
	int n;
	vector<int> r, p;
	UnionFind() {}
	UnionFind(int sz) : n(sz), r(sz, 1), p(sz, 0) { iota(p.begin(), p.end(), 0); }
	int find(int x) {
		return (x == p[x] ? x : p[x] = find(p[x]));
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if ( x == y ) return;
		if( r[x] < r[y] ) swap(x, y);
		r[x] += r[y];
		p[y] = x;
	}
};

struct Edge {
	int to, from, cost;
	bool operator<(const Edge& e) const {
		return cost < e.cost;		
	}
};

int main() {
	int n, m;
	while ( cin >> n >> m, n ) {
		vector<Edge> G;
		for ( int i = 0; i < m; i++ ) {
			int a, b, w;
			cin >> a >> b >> w;
			a--; b--;
			G.push_back({a, b, w});			
		}

		sort(G.begin(), G.end());

		/*for ( int i = 0; i < m; i++ ) {
			cout << G[i].to <<	" " << G[i].from << " "<<			G[i].cost << endl;
			}*/

		int ans = INF;
		for ( int i = 0; i < m; i++ ) {
			int cnt = 0;
			int ma = -1;
			int mi = INF;
			UnionFind uf(n+1);			
			for ( int j = i; j < m; j++ ) {
				Edge e = G[j];
				int a = e.to, b = e.from, w = e.cost;
				//if ( i == 0 ) cout << a << " " << b << endl;
				if ( uf.same(a, b) ) continue;
				cnt++;
				//if ( i == 0 ) cout << cnt << endl;
				ma = max(ma, w);
				mi = min(mi, w);
				if ( cnt >= n-1 ) break;
				uf.unite(a, b);
			}

			if ( cnt >= n-1 ) {
				//cout << 'a' << endl;
				ans = min(ans, ma-mi);
			}
		}

		if ( ans == INF ) cout << -1 << endl;
		else cout << ans << endl;

	}
	
	return 0;
}



Measured memory_bytes: 3288
import sys
input = sys.stdin.buffer.readline

MOD = 10 ** 9 + 7
SIZE = 10 ** 6 + 1

g1 = [1, 1]      # 元テーブル
g2 = [1, 1]      # 逆元テーブル
inverse = [0, 1] # 逆元テーブル計算用テーブル

def comb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % mod

for i in range(2, SIZE + 1):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i) ) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

N, K = map(int, input().split())

answer = 0
for k in range(min(N, K) + 1):
    answer = (answer + comb(N, k, MOD) * comb(N - 1, k, MOD)) % MOD
print(answer)


Measured memory_bytes: 128268
#include<stdio.h>
int main(void)
{
int i,n;
int number;
long long int sum = 0;
int min =0;
int max = 0;

scanf("%d",&n);

for(i=0;i<n;i++)
{
scanf("%d",&number);
if(i==0)
{
min =number;
max = number;
}
if(number<min) min = number;
if(number>max) max = number;

sum += number;
}

printf("%d %d %lld\n",min,max,sum);

return 0;
}

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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define int long long
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>=0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const ll mod = 1e9 + 7;
const ll INF = 1<<30;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

int n, m, k;
int a[20000 + 5];
int dp[20000 + 5];

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    rep(i, n) cin >> a[i];
    fill(dp, dp + n + 1, LLONG_MAX);
    dp[0] = 0;
    rep(i, n){
        int mx = 0;
        int mn = 1e9+5;
        rep(s, m) {
            if (i - s < 0) break;
            mx = max(mx, a[i - s]);
            mn = min(mn, a[i - s]);
            dp[i+1] = min(dp[i + 1], dp[i - s] + k + (s + 1) * (mx - mn));
        }
    }
    cout << dp[n] << endl;
}

Measured memory_bytes: 3516
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; ++i)
#define repR(i, n) for(ll i = n; i >= 0; ++i)
#define FDS(i, n) for(ll i = 0; i < n; ++i)
#define FDSR(i, n) for(ll i = n; i >= 0; ++i)
#define FOR(i, m, n) for(ll i = m; i < n; ++i)
#define FORR(i, m, n) for(ll i = m;i >= n;--i)
#define VSORT(v) sort(v.begin(), v.end());
#define VREV(v) reverse(v.begin(), v.end());
#define INF 999999999
#define itn ll
#define ednl endl
using namespace std;
typedef long long ll;template<typename Typell>Typell G_C_D(Typell a, Typell b){if (a < 0) a = -a;if (b < 0) b = -b;while (b != 0) {a %= b;if (a == 0) return b;b %= a;}return a;}template<typename Typell>
Typell G_C_D(const std::vector<Typell> &list){Typell a = list[0];for (size_t i = 1; i < list.size(); ++i) {a = G_C_D(a, list[i]);}return a;}template<typename Typell>Typell L_C_M(Typell a, Typell b) {if( a == 0 && b == 0)return 0;return a / G_C_D(a, b) * b;}
template<typename Typell>Typell L_C_M(const std::vector<Typell> &list){Typell a = list[0];for (size_t i = 1; i < list.size(); ++i) {a = L_C_M(a, list[i]);}return a;}

int main(){
	cin.tie(0);ios::sync_with_stdio(false);
	ll A,B,C,D;
	cin>>A>>B>>C>>D;
	ll aa=0,bb=0;
	aa=A-A/C-A/D+A/L_C_M(C,D);
	bb=B-B/C-B/D+B/L_C_M(C,D);
	if(A%C==0||A%D==0)cout<<bb-aa<<endl;
    else cout<<bb-aa+1<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

int n;
pi a[200005];

int main(){
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d",&a[i].first);
		a[i].second = 1;
	}
	for(int i=0; i<n; i++){
		scanf("%d",&a[i+n].first);
		a[i+n].second = 2;
	}
	sort(a, a+2*n);
	int cnt = 0;
	lint ans = 1;
	for(int i=0; i<2*n; i++){
		if(a[i].second == 1){
			if(cnt < 0){
				ans *= -cnt;
				ans %= mod;
			}
			cnt++;
		}
		else{
			if(cnt > 0){
				ans *= cnt;
				ans %= mod;
			}
			cnt--;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define mk make_pair
using namespace std;
typedef long long ll;
const int N = 3e2 + 5;
const int mod = 1e9 + 7;
int n, a[N], s[N];
double dp[N][N][N];
int main() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		s[a[i]]++;
	}
	for (int k = 0; k <= n; ++k) {
		for (int j = 0; j <= n; ++j) {
			for (int i = 0; i <= n; ++i) {
				if (i + j + k == 0) continue;
				if (i) dp[i][j][k] += (dp[i - 1][j][k] + 1) * i / n;
				if (j) dp[i][j][k] += (dp[i + 1][j - 1][k] + 1) * j / n;
				if (k) dp[i][j][k] += (dp[i][j + 1][k - 1] + 1) * k / n;
				double p = (double)(n - i - j - k) / n;
				dp[i][j][k] += p;
				dp[i][j][k] /= (1 - p);
			}
		}
	}
	printf("%.10f\n", dp[s[1]][s[2]][s[3]]);
}


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

#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const int N = 10005;
int a[N];
int primes[100005];
bool is_prime(int n){
	for(int j = 2; j * j <= n; j++) if(n % j == 0) return 0;
	return 1;
}

ll f[N];

set<int> get_primes(int n){
	set<int> ret;
	for(int i = 2; i * i <= n; i++) if(n % i == 0){
		while(n % i == 0){n /= i;}
		ret.insert(i);
	}
	if(n != 1) ret.insert(n);
	return ret;
}
int main(){
	int n;
	sd(n);
	int g = 0;
	for(int i = n; i >= 0; i--){
		sd(a[i]);
		g = __gcd(g, abs(a[i]));
	}
	set<int> st = get_primes(g);
	for(int p = 2; p <= n; p++){
		if(!is_prime(p)) continue;
		memset(f, 0, sizeof f);
		ll sm = 0;
		for(int i = 0; i <= n; i++) f[i % (p - 1)] += a[i], sm += a[i];
		
		if(p == 2 && (abs(a[0]) % 2 == 0) && (abs(sm) % 2 == 0)){
			st.insert(2);
			continue;
		}
		bool ok = abs(a[0]) % p == 0;
		for(int i = 0; i < p; i++) if( ((f[i] % p) + p) % p != 0){
			ok = 0;
			break;
		}
		if(ok)st.insert(p);
	}
	for(auto it : st) printf("%d\n", it);
}

Measured memory_bytes: 384
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

void solve() {
  long N, K;
  cin >> N >> K;
  vector<long> l(N);
  rep (i, N) cin >> l[i];
  sort(l.begin(), l.end());
  reverse(l.begin(), l.end());
  long ans = 0;
  rep (i, K) ans += l[i];
  cout << ans << endl;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout.precision(12);
  solve();
  return 0;
}


Measured memory_bytes: 256
import sys
import copy
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	H, W = MAP()
	N = INT()
	A = MAP()
	# print(A)
	
	M = [[0] * W for _ in range(H)]
	# print(M)

	MOVE = [[0,1],[1,0],[0,-1],[-1,0]]

	h, w = 0, 0
	M[0][0] = 1
	A[0] -= 1
	direct = 0
	for i, a in enumerate(A):
		num = i+1
		cnt = a
		if not cnt: continue
		fin = False
		while True:
			for i, move in enumerate(MOVE):
				if i < direct:
					continue
				else:
					direct = 0
					dh, dw = move
				while h+dh < H and h+dh >= 0 and w+dw < W and w+dw >= 0 and M[h+dh][w+dw] == 0:
					h += dh
					w += dw
					M[h][w] = num
					cnt -= 1
					if cnt == 0:
						direct = MOVE.index([dh, dw])
						fin = True
						break
				if fin:	break
			if fin:	break

	for m in M:
		print(' '.join(map(str, m)))

if __name__ == '__main__':
	main()


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

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;

vector<ll> lun;

void rec(ll d, ll n) {
    lun.push_back(n);

    if (d > 10) return;

    for (ll i = -1; i <= 1; ++i) {
        ll t = n % 10 + i;

        if (0 <= t && t <= 9) rec(d + 1, n * 10 + t);
    }
}

int main() {

    ll k; cin >> k;

    for (ll i = 1; i <= 9; ++i) {
        rec(1, i);
    }

    sort(lun.begin(), lun.end());

    cout << lun[k - 1] << endl;
}

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

int main()
{
  int n;
  cin>>n;
  int a[n];
  int flag=0;
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    if(a[i]%2==0)
    {
    	if(a[i]%3==0 || a[i]%5==0)
    	 continue;
    	 else
    	 {
    	 	flag=1; break;
    	 }
    }
  }
  if(!flag) cout<<"APPROVED";
  else cout<<"DENIED";
  return 0;
}
    

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

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int d;
  cin >> d;
  for (int i = 0; i < d; i++) {
    cout << "Case " << i + 1 << ":" << endl;
    string s;
    cin >> s;
    for (int j = 0; j < 10; j++) {
      string t = to_string(stoi(s) * stoi(s));
      while (int(t.size()) < 8) t = "0" + t;
      s = t.substr(2, 4);
      cout << stoi(s) << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 3216
#include<iostream>
#include<algorithm>
using namespace std;

template<typename T>
T gcd(T a,T b)
{
	if(a<b) swap(a,b);
	T r = a % b;
	while(r!=0)
	{
		a = b;
		b = r;
		r = a % b;
	}
	return b;
}

int main()
{
	int T;
	cin >> T;
	bool is_ok[T];
	unsigned long long int A,B,C,D;
	for(int i=0;i<T;i++)
	{
		is_ok[i] = false;
		cin >> A >> B >> C >> D;
		if(A<B) 	continue;
		if(D<B)		continue;
		if(C<A%B)	continue;
		if(C<B-gcd(B,D))	continue;
		is_ok[i] = true;
	}
	for(int i=0;i<T;i++)
		if(is_ok[i]) 	cout << "Yes" << std::endl;
		else			cout << "No" << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    ll a,b,c,k;
    cin >> a >> b >> c >> k;
    if(a+b < k){
        cout << a - (k-(a+b)) << endl;
    }else{
        cout << min(a,k) << endl;
    }
    return 0;
}

Measured memory_bytes: 3620
# frozen_string_literal: true

S = gets.strip

N = S.size
S1 = '0' + S

if S1 == S1.reverse && S[0] == '1'
  center = (N + 1) / 2
  i = 0
  (2..center).each do |j|
    if S1[j] == '1'
      puts "#{i} #{j}" if i != 0
      ((i + 1)...j).each do |k|
        puts "#{j} #{k}"
      end 
      i = j
    end
  end
  puts "#{i} #{N}" if i != 0
  ((i + 1)...N).each do |k|
    puts "#{N} #{k}"
  end
else  
  puts(-1)
end

Measured memory_bytes: 3836
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define SUBS(s,f,t) ((s).substr((f),(t)-(f)))
#define ALL(a) (a).begin(),(a).end()
#define Max(a) (*max_element(ALL(a)))
#define Min(a) (*min_element(ALL(a)))
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,k;cin>>n>>k;
  vi A(n);
  for(auto &a:A)cin>>a;
 
  for(int i=k;i<n;i++){
    if(A[i-k] < A[i])cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
  return 0;
}


Measured memory_bytes: 4764
N = int(input())
A = list(map(int, input().split()))

S = [0] * 3
for a in A:
  S[a-1] += 1
I, J, K = S

dp = [[[0.0] * (N+1) for j in range(N+1)] for i in range(N+1)]

for k in range(S[2] + 1):
  for j in range(S[1] + S[2] - k + 1):
    for i in range(S[0] + S[1] + S[2] - j - k + 1):
      if i == j == k == 0: continue
      dp[i][j][k] = (i * (dp[i-1][j][k] if i > 0 else 0) + j * (dp[i+1][j-1][k] if j > 0 else 0) + k * (dp[i][j+1][k-1] if k > 0 else 0) + N) / (i + j + k)

print(dp[I][J][K])

Measured memory_bytes: 254088
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std ; 

typedef long long ll ; 

int main()
{
    int N ; 
    scanf("%d", &N) ; 
    int cnt = 0 ; 
    for(int i = 0 ; i != N ; i++) {
        int now ; 
        scanf("%d", &now) ; 
        if(now%2)
            cnt++ ; 
    }
    puts((cnt%2) ? "NO":"YES") ; 
    return 0 ; 
}


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

int main() {
  int n,d;
  cin >> n >> d;
  int ans = 0;
  ans = n/(d*2 + 1);
  if(n%(d*2 + 1) != 0){
    cout << ans + 1 << endl;
  }
  else{
    cout << ans << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>

# define REP(i,n) for(int i=0; i<n;i++)

using namespace std;

int main(){
	
	int n;
	cin >> n;
	long long int ans = pow(3,n);
	
	int a;
	int odds=0;
	REP(i,n){
		cin >> a;
		if (a%2==1) odds++;
	}
	
	ans = ans-pow(2,n-odds);
	cout << ans << endl;
	
}


Measured memory_bytes: 384
#include <iostream>
#include <map>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#include <bitset>
#include <type_traits>

#include <list>
using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define YES(j) cout << (j ? "YES" : "NO") << endl;
#define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
#define yes(j) std::cout << (j ? "yes" : "no") << endl;

int main(void)
{
    int n, m;
    cin >> n >> m;
    vector<int> a;
    vector<int> d;
    REP(i, m)
    {
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < m - 1; i++)
    {
        d.push_back(abs(a[i + 1] - a[i]));
    }
    sort(d.begin(), d.end());

    int sum = 0;
    REP(i, m - 1 - n + 1)
    {
        sum += d[i];
    }
    cout << sum << endl;
}

Measured memory_bytes: 1400
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;

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

    ll h, w, K, dp[110][10];
    cin >> h >> w >> K;

    REP(i, 110)
    REP(j, 10)
    dp[i][j] = 0;

    dp[0][1] = 1;

    for (ll i = 0; i <= h; i++)
    {
        ll tmp[10][3];
        for (ll j = 1; j <= w; j++)
        {
            ll d = 0, r = 0, l = 0;
            for (ll k = 0; k < 1 << (w - 1); k++)
            {
                ll k_ = k;
                bool b = true, c = false;
                while (k_ > 0)
                {
                    if (k_ % 2 && c)
                        b = false;

                    if (k_ % 2)
                        c = true;
                    else
                        c = false;

                    k_ /= 2;
                }

                if (!b)
                    continue;

                if (j < w && (k & (1 << (j - 1))))
                {
                    r++;
                }
                else if (1 < j && (k & (1 << (j - 2))))
                    l++;
                else
                    d++;
            }

            tmp[j][0] = (dp[i][j] * r) % MOD;
            tmp[j][1] = (dp[i][j] * l) % MOD;
            tmp[j][2] = (dp[i][j] * d) % MOD;
        }

        for (int j = 1; j <= w; j++)
        {
            dp[i + 1][j + 1] += tmp[j][0];
            dp[i + 1][j - 1] += tmp[j][1];
            dp[i + 1][j] += tmp[j][2];

            dp[i + 1][j + 1] %= MOD;
            dp[i + 1][j - 1] %= MOD;
            dp[i + 1][j] %= MOD;
        }
    }

    if (false)
        REP(i, h + 1)
        {
            REP(j, w)
            {
                cout << dp[i][j + 1] << " ";
            }
            cout << endl;
        }

    cout << dp[h][K] << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
using namespace std;
using ll = long long;
 
int main() {
  ll n;
  cin >> n;
  string ans;
  while(n){
    n--;
    ans += 'a'+n%26;
    n /= 26;
  }
  reverse(ans.begin(),ans.end());
  cout << ans << endl;
}

Measured memory_bytes: 3600
#include <stdio.h>

int main(){
  long int n, now, i;

  scanf("%ld",&n);
  now = n;

  for(i=2; i<=n && now!=1; i++){
    if(now%i==0){
      n = n*(i-1)/i;
      while(now%i==0)
	now/=i;
    }
  }
  printf("%ld\n",n);
  return 0;
}

Measured memory_bytes: 592
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <numeric>
typedef long long Int;
#define rep(i,a,b) for(Int i=a;i<b;++i)
#define rrep(i,a,b) for(Int i=a;i>=b;--i)
using namespace std;

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

  	int N, A; cin >> N >> A;
    if (N%500 <= A) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
function Main(input) {
  const inputArr = input.toString().split("\n");
  const N = inputArr[0];
  var S = inputArr[1];

  var answerCount = 0;

  while (S.search("ABC") !== -1) {
    S = S.replace("ABC", "Z");
    answerCount++;
    // console.log(S);
  }


  console.log(answerCount);

}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7372
#include <string>
#include <vector>
#include <iostream>

using namespace std;

string put_nchar(int n, char c)
{
	string S(n, c);

	return S;
}

void print_frame(int H, int W, char c1, char c2)
{
	cout << put_nchar(W, c1) << endl;

	for(int i = 1; i < H - 1; i++)
	{
		cout << c1 << put_nchar(W - 2, c2) << c1 << endl;
	}

	cout << put_nchar(W, c1) << endl;
}

int main()
{
	vector<int> W, H;

	while(true)
	{
		int H1, W1;

		cin >> H1 >> W1;

		if(H1 == 0 && W1 == 0) { break; }

		H.push_back(H1);
		W.push_back(W1);
	}

	for(vector<int>::size_type i = 0; i < H.size(); i++)
	{
		print_frame(H[i], W[i], '#', '.');

		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 1216
from collections import deque

n,m = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

ok = False
for v in G[0]:
    s = G[v]
    if n-1 in s:
        ok = True

if ok:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 42028
n, m, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A_cum, B_cum = [0], [0]
for i, a in enumerate(A):
    A_cum.append(A_cum[i] + a)
for i in range(m):
    B_cum.append(B_cum[i] + B[i])

ans = 0
best = m
for i in range(n+1):
    a_time = A_cum[i]
    for j in range(best, -1, -1):
        if B_cum[j] <= k - a_time:
            ans = max(ans, i + j)
            break
    best = j
print(ans)

Measured memory_bytes: 47344
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

int tmp[200001], tmp2[200001];
void pakuripair_sort(int N, int A[], int B[]) {
	const int b = 8;
	rep(k, 4) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) {
			tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
			tmp2[kazu[A[i] >> k * b & ((1 << b) - 1)]] = B[i];
		}
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) {
			A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
			B[kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp2[i];
		}
	}
}

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


	int N = getint(), K = getint();
	int A[200001];
	rep(i, N) {
		A[i] = (getint() + K - 1) % K;
	}

	int B[200001];
	B[0] = 0;
	rep(i, N) {
		B[i + 1] = B[i] + A[i];
		if (B[i + 1] >= K) B[i + 1] -= K;
	}
	rep(i, N + 1) A[i] = i;

	pakuripair_sort(N + 1, B, A);
	int kazu = 0;
	int mae = B[0];
	rep(i, N + 1) tmp[i] = 0;
	rep(i, N + 1) {
		if (mae != B[i]) {
			kazu++;
			mae = B[i];
		}
		tmp[A[i]] = kazu;
	}
	rep(i, N + 1) A[i] = 0;

	ll kotae = 0;
	rep(i, N + 1) {
		kotae += A[tmp[i]];
		A[tmp[i]]++;
		if (i - K + 1 >= 0) A[tmp[i - K + 1]]--;
	}

	printf("%lld", kotae);

	Would you please return 0;
}

Measured memory_bytes: 3456
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath> 
#include<cstring> 
#include<cassert>
#include<string>
#include<sstream>
#include<fstream>
#include<deque>
#include<queue>
#include<vector>
#include<map>
#include<list>
#include<stack>
#include<set>
#include<bitset>
#include<iomanip>
#include<utility>
#include<functional>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cwchar>
#include<cwctype>
#include<exception>
#include<locale>
#include<numeric>
#include<new>
#include<stdexcept>
#include<limits>
using namespace std;

#define ll long long
#define INF 1e9
#define rep(i,n) for(int (i)=0;(i)<n;i++)
#define REP(i,n) for(int (i)=1;(i)<=n;i++)
#define repd(i,n) for(int (i)=n-1;(i)>=0;i--)
#define REPD(i,n) for(int (i)=n;(i)>0;i--) 
#define mk(a,b) make_pair(a,b)
#define fi first
#define se second
#define pii pair<int,int>
#define All(s) (s.begin(),s.end())

const int maxn=100005;
int n;
vector<int>edge[maxn],path;
int p[maxn],sz[maxn];

void dfs(int x,int par){
	p[x]=par;
	sz[x]=1;
	rep(i,edge[x].size()){
		int y=edge[x][i];
		if(y!=par)dfs(y,x),sz[x]+=sz[y];
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	rep(i,n-1){
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs(1,-1);
//	REP(i,n)cout<<sz[i]<<endl;
	int cur=n;
	while(cur!=-1)path.push_back(cur),cur=p[cur];
	reverse(path.begin(),path.end());
	if(path.size()%2==0){
		int k=path.size()/2;
		int A=n-sz[path[k]]-k,B=sz[path[k]]-k;
		if(A>B){
			cout<<"Fennec";
		}
		else cout<<"Snuke";
	}
	else{
		int k=path.size()/2+1;
		int A=n-sz[path[k]]-k,B=sz[path[k]]-k+1;
//		cout<<k<<" "<<path[k]<<" "<<A<<" "<<B<<endl;
		if(A>=B){
			cout<<"Fennec";
		}
		else cout<<"Snuke";
	}
	return 0;
}
/*
9
1 2
1 5
1 6
2 3
3 4
4 9
7 9
8 9
*/

Measured memory_bytes: 14972
#include <stdio.h>
#include <list>
#include <string>
using namespace std;

void print(const list<int> &values) {
    bool flag = false;
    for (const auto &v : values) {
        if (flag) printf(" ");
        printf("%d", v);
        flag = true;
    }
    printf("\n");
}

void deleteFirst(list<int> &values) {
    values.pop_front();
}

void deleteLast(list<int> &values) {
    values.pop_back();
}

void deleteValue(list<int> &values, int x) {
    for(auto it = values.begin(); it != values.end(); it++) {
        if (*it == x) {
            values.erase(it);
            break;
        }
    }
}

void insert(list<int> &values, int x) {
    values.push_front(x);
}

int main() {
    int n;
    scanf("%d", &n);

    list<int> values;

    for (int i = 0; i < n; i++) {
        char tmpCommand[20];
        int x = 0;
        scanf("%s", tmpCommand);

        string command = string(tmpCommand);
        if (command == "insert") {
            scanf("%d", &x);
            insert(values, x);
        } else if (command == "delete") {
            scanf("%d", &x);
            deleteValue(values, x);
        } else if (command == "deleteFirst") {
            deleteFirst(values);
        } else if (command == "deleteLast") {
            deleteLast(values);
        }
    }

    print(values);
}

Measured memory_bytes: 34080
#include<bits/stdc++.h>
	#define tmp(x) std::cout<<"& "<<(x)<<" &\n"
	#define rep(i,a,b) for(int i=(a);i<=(b);++i)
	#define per(i,a,b) for(int i=(a);i>=(b);--i)
	typedef long long ll;
	
	using namespace std;
	const int maxn=2e5+100;
	int n,k;
	int a[maxn];
	bool work(double val){
	    int ans=0;
	    rep(i,1,n){
	        if(a[i]<=val)continue;
	        int v=1.0*a[i]/val;
	        v+=(a[i]>1.0*v*val)-1;
	           ans+=v;
	        if(ans>k)return false;
	    }
	    return true;
	}
	
	
	int main(){
	//	freopen("in.txt","r",stdin);
	    ios::sync_with_stdio(false);
	    cin.tie(0);
	    cin>>n>>k;
	    rep(i,1,n)cin>>a[i];
	    int l=0,r=1000000000;
	    
	    while(l+1<r){
	        int mid=(l+r)/2;
	        if(work(1.0*mid))r=mid;
	        else l=mid+1;
	    }
	
	
	
	     if (l!=0&&work(l))printf("%d",l);
	//	 else if(work(1.0*l+0.499999999))	printf("%d",l);
	     else printf("%d",r);
	
	
	    return 0;
	}

Measured memory_bytes: 4332
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
/*cheated*/
int main(){
	string s;
	cin >> s;
	string t[4]={"dream","dreamer","erase","eraser"};
	reverse(s.begin(),s.end());
	for(int i=0;i<4;i++) reverse(t[i].begin(),t[i].end());
	bool can = true;
	for(int i=0;i<s.size();)
	{
		bool can2 = false;
		for(int j=0;j<4;j++)
		{
			string d =t[j];
			if(s.substr(i,d.size())==d)
			{
				i+=d.size();
				can2=true;
			}			
		}
		if(can2==false)
		{
				can=false;
				break;
		}
	}
	if(can) cout << "YES";
	else cout << "NO";
	return 0;
}

Measured memory_bytes: 512
N,M=map(int,input().split())
S=input()
T=input()

def gcd(a,b):
  if a<b:
    a,b=b,a
  while a%b>0:
    a,b=b,a%b
  return b

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

length=lcm(N,M)
gapt=length//N
gaps=length//M
i=0
j=0
while i<N:
  if S[i]!=T[j]:
    print(-1)
    break
  else:
    i+=gaps
    j+=gapt
else:
  print(length)

Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>
#include <bitset>
#include <cstdio>
#include <set>
//#include <bits/stdc++.h>
#define rep(i,n) Rep(i,0,n)
#define Rep(i,k,n) for(int i=k ; i<n ; i++)
#define rep1(i,n) for(int i=1 ; i<=n ; i++)
#define vi vector<int>
#define vii vector<int,int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())

//const int MOD = 1000000007;
//const int INF = 1<<30;
using namespace std;

string yn(bool x){
    return x ? "Yes" : "No";
}
int main()
{
    int n; cin >> n;
    char name[n][12];
    
    rep(i,n) {
        scanf("%s",name[i]);
        //cin >> name[i];
    }
    
    long long a[5] = {0,0,0,0,0};
    string c = "MARCH";
    
    rep(i,n) {
        rep(j,5){
            if(name[i][0]==c[j]) a[j]++;
        }
    }
    
    long long ans = 0;
    rep(i,3){
        Rep(j,i+1,4){
            Rep(k,j+1,5){
                ans += a[i]*a[j]*a[k];
            }
        }
    }
    
    cout << ans << endl;
        
        
}



Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define pb push_back
#define COUT(x) cout << (x) << endl
#define ENDL cout << endl
#define DF(x) x.erase(x.begin());  // 先頭文字削除
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1000000000;

int main() {
    ll N, M;
    cin >> N >> M;
    ll count = 0;
    rep(i, M) {
        int a;
        cin >> a;
        count += a;
    }
    if (N < count) {
        COUT(-1);
        return 0;
    }
    COUT(N - count);
    return 0;
}

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

using namespace std;
double d[10][10];double rez=0;
struct punct{
    int x;
    int y;
};

int n;
double dist(int x,int y,int x1,int y1){

    return double (sqrt((x-x1)*(x-x1) + (y-y1)*(y-y1)));

}

bool ok(int vaz[], int n , int nr)
{
    for(int i=1; i<=n-1; ++i)
    {
        if(vaz[i]==nr) return 0;
    }
    return 1;
}
int vaz[121]={};

double suma(int vaz[])
{
    double sum=0;
    for(int i=1; i<n; ++i)
    {
        sum+= d[vaz[i]][vaz[i+1]];
    }

    return sum;
}

void backtracking( int k)
{

    for(int i=1; i<=n; ++i)
    {

            vaz[k]=i;
            if(ok(vaz,k,i)){
            if(k==n)
            {
                rez += suma(vaz);
            }
            else{
                backtracking(k+1);
            }
            }
    }


}


int main()
{

    punct a[111];
    cin>>n;


    int b[10]={};
    for(int i=1; i<=n; ++i)
    {
        cin >> a[i].x;
        cin >> a[i].y;
    }


    for(int i=1; i<=n; ++i)
    {
        for(int j= i +1; j<=n; ++j)
        {
             d[i][j] = dist(a[i].x,a[i].y,a[j].x,a[j].y); /// drumul de la i la j
            d[j][i]=d[i][j];
        }
    }
    backtracking(1);
    int impartitor=1;
    for(int i=2; i<=n; ++i)
    {
        impartitor*=i;
    }
    cout<< fixed << setprecision(7) << rez / impartitor ;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < b; i++)
using namespace std;

int main() {
    int l;
    cin >> l;
    
    double x = (double)l / 3;
    double ans = pow(x, 3);

    cout << fixed << setprecision(10) << ans << endl;

    return 0;
}

Measured memory_bytes: 256