akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }


struct UnionFind {
	vector<int> data;
	void init(int n) { data.assign(n, -1); }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
};

int main() {
	int A, B;
	while (~scanf("%d%d", &A, &B)) {
		const int X = 40, Y = 20;
		int H = (Y + 1) * 4, W = X * 2 + 1;
		vector<string> ans(H, string(W, '.'));
		rep(i, H / 2 - 1) rep(j, W)
			ans[i][j] = '#';
		rep(j, W - 1) ans[H / 2][j] = '#';
		ans[H / 2 - 1][0] = '#';
		ans[H / 2 + 1][0] = '#';
		int k = Y * X;
		rep(j, X) rep(i, Y) {
			int y = i * 2 + 1, x = j * 2 + 1;
			ans[y][x] = '.';
			if (k >= A) ans[y + 1][x] = '.';
			ans[H - 1 - y][x] = '#';
			if (k >= B)ans[H - 1 - (y + 1)][x] = '#';
			-- k;
		}
		printf("%d %d\n", H, W);
		for (auto &&s : ans)
			puts(s.c_str());
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define pfi(a) printf("%d",a);
#define pfl(a) printf("%lld",a);
#define pfin(a) printf("%d\n",a);
#define pfln(a) printf("%lld\n",a);
#define sfi(a) scanf("%d",&a);
#define sfl(a) scanf("%lld",&a);
#define pb push_back
#define F first
#define S second
#define vi vector<int>
#define vl vector<long long>
#define vs vector<string>
#define vpp vector<pair<long long,long long>>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define d0(x) cout<<(x)<<" "
#define c1(x) cin>>(x)
#define c2(x,y) cin>>(x)>>(y)
#define c3(x,y,z) cin>>(x)>>(y)>>(z)
#define c4(w,x,y,z) cin>>(w)>>(x)>>(y)>>(z)
#define d1(x) cout<<(x)<<endl
#define d2(x,y) cout<<(x)<<" "<<(y)<<endl
#define d3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define d4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl
#define d5(a,b,c,d,e) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<" "<<(e)<<endl
#define fo(i,a,b) for(int i=a;i<b;i++)
#define alld(c) (c).rbegin(),(c).rend()
#define alli(c) (c).begin(),(c).end()
#define ll long long
const int M=1e9+7;

int main()
{
	int t=1;
	while(t--)
	{
		int n; cin>>n;
		int rem=(n+999)/1000;
		int ans=rem*1000-n;
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 3600
#C
S=input()
K=int(input())
num='23456789'
if S[0]!='1':
    print(int(S[0]))
else:
    n=1
    while True:
        if n==len(S):
            n-=1
            break
        elif S[n]!='1':
            break
        n+=1
    if K-1<n:
        print(1)
    else:
        print(int(S[n]))

Measured memory_bytes: 3060
#!/usr/bin/env python
import sys
sys.setrecursionlimit(100000000)

n, m = list(map(int, input().split()))
c = list(map(int, input().split()))
DP = {}

# num 番目までのコインを使い、yen 円支払うときに必要な枚数
def func(num, yen):
	if num < 0 or yen < 0:
		return 10 ** 18
	if num == 0 and yen == 0:
		return 0
	if not (num, yen) in DP:
		DP[(num, yen)] = min(func(num - 1, yen), func(num, yen - c[num]) + 1)
	return DP[(num, yen)]

print(func(m - 1, n))



Measured memory_bytes: 190800
from math import hypot,atan2
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]
xy = sorted(XY, key=lambda x:atan2(x[1],x[0]))
xy += xy

ans = 0
for i in range(N):
    sx = sy = 0
    for j in range(N):
        x,y = xy[i+j]
        sx += x
        sy += y
        d = hypot(sx,sy)
        if d > ans:
            ans = d
print(ans)

Measured memory_bytes: 3188
n=int(input())
a=list(map(int,input().split()))
x=[]
ans=1

for i in range(n-1):
  if a[i+1]==a[i]:
    continue
  x.append(a[i+1]-a[i])
  
flag=True

for i in range(len(x)-1):
  if flag==False:
    flag=True
    continue
  if x[i]<0 and x[i+1]>0 or x[i]>0 and x[i+1]<0:
    ans+=1
    flag=False
    

print(ans)


Measured memory_bytes: 90868
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;

#define LL long long
const LL MOD = 1000000007;
const int maxn = 100000 + 100;
int n, k, u, v;
LL ans;
LL dp[maxn];
vector<int> G[maxn];

void dfs(int f, int x) {
    ans = ans * dp[x] % MOD;
    int len = G[x].size();
    int cut = 0;
    if(f == 0) {
        cut = 1;
    } else {
        cut = 2;
    }
    for(int i = 0; i < len; ++i) {
        int pos = G[x][i];
        if(pos == f) {
            continue;
        }
        dp[pos] = k - cut;
        ++cut;
        dfs(x, pos);
    }
}

int main() {
    ios::sync_with_stdio(false);

    while(scanf("%d%d", &n, &k) != EOF) {
        ans = 1;
        for(int i = 1; i <= n; ++i) {
            G[i].clear();
        }
        for(int i = 1; i < n; ++i) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        if(n == 1) {
            printf("%d\n", k);
            continue;
        }
        dp[1] = k;
        dfs(0, 1);
        printf("%lld\n", ans);
    }

    return 0;
}

Measured memory_bytes: 11264
fun main(args: Array<String>) {
    abc119b()
}

fun abc119b() {
    val n = readLine()!!.toInt()
    val xvList = (1..n).map { readLine()!!.split(" ") }

    val damas = xvList
        .map { if (it[1] == "JPY") it[0].toDouble() else it[0].toDouble() * 380000.0 }

    val answer = damas.sum()

    println(answer)
}


Measured memory_bytes: 37568
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

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

  int n, k;
  cin >> n >> k;

  k = min(k, n - 1);
  combination c(n);
  mint ans = 0;

  rep(i, k + 1) {
    ans += c(n, i) * c(n-1, i);
  }

  cout << ans.x << endl;
  return 0;
}


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

using namespace std;

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

typedef complex<double> P;
typedef vector<P> polygon;

double eps = 1e-10;

struct line : public vector<P> {
  line(P const& a, P const& b) {
    push_back(a), push_back(b);
  }
};

double dot(P const& a, P const& b) {
  return real(conj(a)*b);
}

double cross(P const& a, P const& b) {
  return imag(conj(a)*b);
}

int ccw(P const& p0, P a, P b) {
  a -= p0, b -= p0;
  if(cross(a, b) > eps) return +1;
  if(cross(a, b) < -eps) return -1;
  if(dot(a, b) < -eps) return +2;
  if(norm(a) < norm(b)) return -2;
  return 0;
}

P crosspoint(line const& a, line const& b) {
  auto va = a[1] - a[0], vb = b[1] - b[0];
  double d = cross(vb, va);
  if(abs(d) < eps) return b[0];
  return a[0] + va * cross(vb, b[1] - a[0]) * (1.0 / d);
}

double area(polygon const& g) {
  double ret = 0;
  rep(i, g.size()) {
    ret += cross(g[i], g[(i+1)%g.size()]);
  }
  return abs(ret) / 2.0;
}

polygon convex_cut(polygon const& g, line const& l) {
  polygon ret;
  int n = g.size();
  rep(i, n) {
    auto cp = g[i%n], np = g[(i+1)%n];
    if(ccw(l[0], l[1], cp) != -1) ret.push_back(cp);
    if(ccw(l[0], l[1], cp) * ccw(l[0], l[1], np) < 0) {
      ret.push_back(crosspoint(line(cp, np), l));
    }
  }
  return ret;
}

int main() {

  for(int N; cin >> N && N;) {
    vector<polygon> gs{polygon{P(-100, -100), P(100, -100), P(100, 100), P(-100, 100)}};
    rep(k, N) {
      double x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
      line L(P(x1, y1), P(x2, y2));
      line R(P(x2, y2), P(x1, y1));
      vector<polygon> ngs;
      for(auto& e: gs) {
        auto left = convex_cut(e, L);
        auto right = convex_cut(e, R);
        if(area(left) > eps) ngs.push_back(left);
        if(area(right) > eps) ngs.push_back(right);
      }
      gs = ngs;
    }
    cout << gs.size() << endl;
  }

  return 0;
}

Measured memory_bytes: 4624
//  __      __       .__           .____________                   __________        __ ________   __                 
// /  \    /  \ ____ |_________  __| _\______   \__ __  ____  _____\______   \__ ___/  |\_____  \ |  | ______  ___.__.
// \   \/\/   _/ __ \|  \_  __ \/ __ | |    |  _|  |  \/ ___\/  ___/|    |  _|  |  \   __/   |   \|  |/ \__  \<   |  |
//  \        /\  ___/|  ||  | \/ /_/ | |    |   |  |  / /_/  \___ \ |    |   |  |  /|  |/    |    |    < / __ \\___  |
//   \__/\  /  \___  |__||__|  \____ | |______  |____/\___  /____  >|______  |____/ |__|\_______  |__|_ (____  / ____|
//        \/       \/               \/        \/     /_____/     \/        \/                   \/     \/    \/\/     

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define ff first
#define ss second
#define PI 3.14159265358979323846
#define endl '\n'

using namespace std;

void solve()
{
    int n;
    cin >> n;
    int cnt = 0;
    queue <ll> q;
    for(int i = 1; i < 10; i++)
        q.push(i);
    while(true)
    {
        ll x = q.front();
        q.pop();
        cnt++;
        if(cnt == n)
        {
            cout << x << endl;
            return;
        }
        if(x % 10 > 0)
            q.push(x * 10 + x % 10 - 1);
        q.push(x * 10 + x % 10);
        if(x % 10 < 9)
            q.push(x * 10 + x % 10 + 1);
    }
}

int main()
{
	int q = 1;
	//scanf("%d", &q);
	for(int i = 1; i <= q; i++)
	{
		solve();
	}
	return 0;
}

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

int main(){
  int n,ac=0,wa=0,tle=0,re=0;
  string s;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> s;
    if(s=="AC")ac++;
    if(s=="WA")wa++;
    if(s=="TLE")tle++;
    if(s=="RE")re++;
  }
    
  cout << "AC x ";
  cout << ac << endl;
  cout << "WA x ";
  cout << wa << endl;
  cout << "TLE x ";
  cout << tle << endl;
  cout << "RE x ";
  cout << re << endl;
}

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

int main(){
    int k;
    string s;
    cin >> k >> s;
    if(s.length() <= k){
        cout << s << endl;
    }else if(s.length() > k){
        rep(i,k){
        cout << s[i] ;
        }
        cout << "..." << endl;
    }
}

Measured memory_bytes: 3632
#include <iostream>
#include <string>
#include <math.h>

using namespace std;

int main(){
    string input1;
    string input2;
    string output;

    int index = 0;
    cin >> input1;
    cin >> input2;

    output = input1 + input2;

    int outnum = stoi(output);

    //heihousuu hanntei

    if( (int)sqrt(outnum) * (int)sqrt(outnum) == outnum){
        cout << "Yes";

    }else{
        cout << "No";
    }


    return 0;

}

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

using namespace std;

int main() {
	int A, B, K;

	cin >> A >> B >> K;

	int i;
	for (i = A; i <= min(A + K - 1, B); i++) {
		cout << i << endl;
	}

	for (i = max(B - K + 1,i); i <= B; i++) {
		cout << i << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

#define N 25
#define NIL -1

struct Node{
  int p,l,r;
};

struct Node T[N];
int n,D[N],H[N];

void setDepth(int,int);
int setHeight(int);
int getSibling(int);
void print(int);
void preorder(int);
void inorder(int);
void postorder(int);

int main(void){
  int v,l,r,root=0;
  int i,j;

  scanf(" %d",&n);
  for(i = 0; i < n; i++)T[i].p = NIL;

  for(i = 0; i < n; i++){
    scanf(" %d %d %d",&v,&l,&r);
    T[v].l = l;
    T[v].r = r;
    if(l != NIL) T[l].p = v;
    if(r != NIL) T[r].p = v;
  }

  for(i = 0; i < n; i++){
    if(T[i].p == NIL) root = i;
  }

  setDepth(root,0);
  setHeight(root);

  printf("Preorder\n");
  preorder(root);
  printf("\n");
  printf("Inorder\n");
  inorder(root);
  printf("\n");
  printf("Postorder\n");
  postorder(root);
  printf("\n");
  
  return 0;
}

void setDepth(int u, int d){
  if(u == NIL) return;
  D[u] = d;
  setDepth(T[u].l,d+1);
  setDepth(T[u].r,d+1);
}

int setHeight(int u){
  int h1=0,h2=0;
  if(T[u].l != NIL){
    h1 = setHeight(T[u].l)+ 1;
  }
  if(T[u].r != NIL){
    h2 = setHeight(T[u].r)+ 1;
  }
  return H[u] = (h1 > h2 ? h1 : h2);
}

int getSibling(int u){
  if(T[u].p == NIL)return NIL;
  if(T[T[u].p].l != u && T[T[u].p].l != NIL){
    return T[T[u].p].l;
  }
  if(T[T[u].p].r != u && T[T[u].p].l != NIL){
    return T[T[u].p].r;
  }
  return NIL;
}

void print(int u){
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("sibling = %d, ",getSibling(u));
  int deg = 0;
  if(T[u].l != NIL)deg++;
  if(T[u].r != NIL)deg++;
  printf("degree = %d, ",deg);
  printf("depth = %d, ",D[u]);
  printf("height = %d, ",H[u]);

  if(T[u].p == NIL){
    printf("root\n");
  }
  else if(T[u].l == NIL && T[u].r == NIL){
    printf("leaf\n");
  }
  else{
    printf("internal node\n");
  }
}

void preorder(int u){
  printf(" %d",u);
  if(T[u].l != NIL) preorder(T[u].l);
  if(T[u].r != NIL) preorder(T[u].r);
}

void inorder(int u){
  if(T[u].l != NIL) inorder(T[u].l);
  printf(" %d",u);
  if(T[u].r != NIL) inorder(T[u].r);
}

void postorder(int u){
  if(T[u].l != NIL) postorder(T[u].l);
  if(T[u].r != NIL) postorder(T[u].r);
  printf(" %d",u);
}



Measured memory_bytes: 2052
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct S{
  int time, lap;
  int rem;  
};
bool operator < (S a, S b)
{
  return a.time < b.time;
}

int main(void)
{
  int n;
  while( cin >> n && n ){
    vector<S> lane[2];
    for(int i=0; i<n; ++i){
      S s;
      cin >> s.time >> s.lap;
      s.rem = s.time;
      lane[0].push_back( s );
    }
    sort( lane[0].begin(), lane[0].end() );
    int time = 0;
    while( lane[0].size() | lane[1].size() ){
      
      for(int i=0; i<2; ++i){
	for(int j=0; j<lane[i].size(); ++j){
	  if( j ) lane[i][j].rem = max( lane[i][j].rem-1, lane[i][j-1].rem );
	  else lane[i][j].rem--;
	}
      }

      vector<S> tmp[2];
      for(int i=0; i<2; ++i){
	for(int j=0; j<lane[i].size(); ++j){
	  if( lane[i][j].rem == 0 ){
	    tmp[i].push_back( lane[i][j] );
	    tmp[i].back().rem = tmp[i].back().time;
	    lane[i].erase( lane[i].begin() + j );
	    --j;
	  }
	}
	sort( tmp[i].begin(), tmp[i].end() );
      }
      
      for(int i=0; i<tmp[0].size(); ++i){
	lane[1].push_back( tmp[0][i] );
      }

      for(int i=0; i<tmp[1].size(); ++i){
	if( --tmp[1][i].lap ){
	  lane[0].push_back( tmp[1][i] );
	}
      }
      
      ++time;
    }
    cout << time << endl;
  }
  return 0;
}

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

using namespace std;

#define ld long double
#define ll long long int
#define endl '\n'
#define check_time() cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1e9+7
#define INF 0x3f3f3f3f
#define maxarr(A,n) *max_element(A,A+n) 
#define minarr(A,n) *min_element(A,A+n);
#define ft first
#define sd second
#define all(v) (v.begin(),v.end())
#define vll vector<ll> 
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define pb push_back
#define show(x) cout<<#x<<" "<<x<<endl;
#define PI 3.14159265358979323846

void solve()
{
	ld a,b,h,m,angh,angm,fang,ans;ld val;
	cin>>a>>b>>h>>m;
	cout<<fixed<<setprecision(20);
	angh=30*h;
	angm=6*m;
	angh+=(m/2);
	fang=abs(angh-angm);
	fang=min(fang,360-fang);
	//show(fang);
	
	if(fang==90)
		val=0;
	else if(fang==0)
		val=1;
	else if(fang==180)
		val=-1;
	else
	{
		fang*=(PI/180);
		val=cos(fang);
	}
	
	//show(cos(fang));
	ans=(a*a)+(b*b)-(2*a*b*val);
	cout<<sqrt(ans)<<endl;
	//cin>>a;
}

int main()
{
	fastio();

	ll T=1;	//cin>>T;
	while(T--) solve();
	
	//check_time();
	return 0;   
}   



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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, w;
    cin >> n >> w;
    vector<int> we(n), va(n);
    for (int i = 0; i < n; ++i) {
        cin >> we[i] >> va[i];
    }
    vector<long long> dp(w + 1);
    for (int i = 0; i < n; ++i) {
        for (int j = w - we[i]; j >= 0; --j) {
            dp[j + we[i]] = max(dp[j + we[i]], dp[j] + va[i]);
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << '\n';
    return 0;
}

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

using namespace std;

#define DUMP(x) std::cerr << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")
#define imp puts("impossible")
#define M1 puts("-1")
#define pb push_back

template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using pll = pair<ll, ll>;
using setint = set<int32_t>;
using setstr = set<string>;
using qint = queue<int32_t>;
using qpint = queue<pint>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

void Main()
{
    int n, k;
    cin >> n >> k;
    vint a(n);
    rep(i, n) cin >> a[i];

    rep(i, n)-- a[i];
    vint s(n + 1);
    rep(i, n)
    {
        s[i + 1] = (s[i] + a[i]) % k;
    }
    map<int, int> mp;
    ll ans = 0;
    qint q;
    rep(i, n + 1)
    {
        DUMP(s[i]);
        ans += mp[s[i]];
        ++mp[s[i]];
        q.push(s[i]);
        if ((int)q.size() >= k)
        {
            --mp[q.front()];
            q.pop();
        }
    }
    cout << ans << endl;
}

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 12032
using System;
class atcoder{
    public static void Main(){
        string[] s = Console.ReadLine().Split(' ');
        int n = int.Parse(s[0]);
        int m = int.Parse(s[1]);
        if ((n + m) % 2 == 0){
            Console.WriteLine((n + m) / 2);
        }else{
            Console.WriteLine("IMPOSSIBLE");
        }

    }
}

Measured memory_bytes: 13140
from math import cos, pi

A, B, H, M = map(int, input().split())

theta = abs(M * 6 - (H * 30 + M / 2)) / 360 * 2 * pi
c = (A ** 2 + B ** 2 - 2 * A * B * cos(theta)) ** 0.5
print(c)


Measured memory_bytes: 62168
n,m = map(int,input().split())

ab = []
c = []
for _ in range(m):
    ab_i = tuple(map(int,input().split()))
    ab.append(ab_i)
    c_i = tuple(map(int,input().split()))
    c_i_bit = 0
    for j in c_i:
        c_i_bit += 1 << (j-1)
    c.append(c_i_bit)

inf = 10**10
dp = [ [inf] * 2**n for _ in range(m+1) ]
dp[0][0] = 0

for i in range(m):
    for j in range(2**n):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][j|c[i]] = min(dp[i+1][j|c[i]], dp[i][j] + ab[i][0])

ans = dp[-1][-1]
if(ans == inf):
    print(-1)
else:
    print(ans)

Measured memory_bytes: 78936
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>
#include <climits>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
typedef unsigned long ul;
typedef pair<ul, ul> P;




int main()
{
    int N,K;
    cin >> N;
	cin >> K;

	vector<int> h;
	int r;
	REP(i, N)
	{
		cin >> r;
		h.push_back(r);
	}
	sort(h.begin(), h.end());
	int min = INT_MAX;
	
	REP(i, N - K+1)
	{
		
		if (h[i + K-1] - h[i] < min)
		{
			min = h[i + K-1] - h[i];
		}
	}
	cout << min << endl;

	return 0;
}

Measured memory_bytes: 892
#include<bits/stdc++.h>
#define maxi 200005
using namespace std;
int main()
{
   int a,b,c,d,h=0,f=0;
   cin>>a>>b>>c>>d;
   int res1=a/d;
   if(a%d!=0)
   {
       res1++;
   }
   int res2=c/b;
   if(c%b!=0)
   {
       res2++;
   }
   if(res1>=res2)printf("Yes");
   else printf("No");
}


Measured memory_bytes: 3764
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define br cout << endl;
using namespace std;
const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<ll>>;
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;}

// 0 false, 1 true 
// stringの数字をint型にしてアスキーコードになったら -48する
// 切り上げ　ceil(a)


int main() {
    string s;
    cin >> s;
    int n = stoi(s);
    int size = s.size();

    unordered_map<ll, ll> mp;

    rep(i,n){
        string tmp = to_string(i+1);
        ll first = tmp.at(0) - 48;
        ll last = tmp.at(tmp.size()-1) - 48;
        mp[10*first + last]++;
    }

    ll ans = 0;
    for(ll i = 1; i < 10; i++){
        for(ll j = 1; j < 10; j++){
            ans += mp[i*10 + j] * mp[j*10 + i];
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
typedef long long ll;
#define _GLIBCXX_DEBUG
typedef vector<int> vec;
typedef vector<ll> lvec;
typedef vector<char>cvec;
typedef pair<ll, ll> LP;
typedef tuple<ll, ll, ll> LT;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
int main()	{
  int n;
  cin>>n;
  vector<int>h(n);
  rep(i,n) cin>>h[i];
  int cnt=0,ans=0;
  rep(i,n-1){
    if(h[i]>=h[i+1])
      cnt++;
    else{
      ans=max(cnt,ans);
      cnt=0;
    }
  }
  ans=max(cnt,ans);
  cout<<ans<<endl;
}

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


int main(){
	int N;cin >> N;
	cout <<( 1+N)*N/2 << endl;
	return 0;
}













Measured memory_bytes: 3556
#include <iostream>
#include<algorithm>
#include<string>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#include <iomanip>
#pragma region Macros
#define int long long
#define double long double
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define LAST(x) x[x.size()-1]
#define ALL(x) (x).begin(),(x).end()
#define swap(a,b) (a += b,b = a - b,a -= b)
#define CEIL(a,b) ((a+b-1)/b)
int FACT(int a) {
	if (a == 0)
		return 1;
	else
		return a * FACT(a - 1);
}
int nPr(int n, int r) {
	int s = n-r+1;
	int sum = 1;
	for(int i =s;i<=n;i++)
		sum *= i;
	return sum;
}
//int nCr1(int n, int r)
//int nCr2(int n, int r) 
int GCD(int a, int b) // assuming a,b >= 1
{
	if (a < b)
		swap(a, b);
	if (b == 0)
		return a;
	if (a % b == 0)
		return b;
	return GCD(b, a % b);
}
int LCM(int a, int b) // assuming a,b >= 1
{
	return  a * b / GCD(a, b);
}
double LOG(int a, int b) {
	return log(b) / log(a);
}
inline bool BETWEEN(int x, int min, int max) {
	if (min <= x && x <= max)
		return true;
	else
		return false;
}

using namespace std;
#pragma endregion
signed main() {
	int N;
	cin >> N;
	if (N % 2 == 0)
		cout << (N / 2) - 1;
	else
		cout << N / 2;
}

Measured memory_bytes: 256
def main():
    S = input()
    l = len(S)
    ans = "Yes"
    for i in range(l):
        if (i % 2 == 0 and S[i] == "L") or (i % 2 != 0 and S[i] == "R"):
            ans = "No"
            break
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3064
#include<cstdio>
#include<string>
#include<vector>
#include<iostream>
#define mod 1000000007
using namespace std;
int main(){
    int n,p[100],a[100]={},b;
    string s[100];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i]>>p[i];
    }
    for(int i=0;i<n;i++){
        b=-1;
        for(int j=0;j<n;j++){
            if(a[j]==0&&(b==-1||s[b]>s[j]||(s[b]==s[j]&&p[b]<p[j]))){
                b=j;
            }
        }
        a[b]=1;
        printf("%d\n",b+1);
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;

int main() {
	while(true){
		int x,y;
		cin >> x >> y;
		
		if(x == 0 && y == 0) break;
		
		if(x > y) cout << y << ' ' << x << endl;
		else cout << x << ' ' << y << endl;
	}
	
}

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<ll, int> pii;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cout << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

#define MN 3010
#define INF (1LL<<60)

//!!!!!!overflow
struct edge {
	int to, cap, rev;
	ll cost;
	edge(int to, int cap, ll cost, int rev) : to(to), cap(cap), cost(cost), rev(rev){}
};

int N;
vector<edge> g[MN];
ll h[MN], dst[MN];
int prevv[MN], preve[MN];

inline void add_edge(int f, int t, int cap, ll cost) {
	g[f].emplace_back(t, cap, cost, (int)g[t].size());
	g[t].emplace_back(f, 0, -cost, (int)g[f].size() - 1);
}

ll min_cost_flow(int s, int t, int f) {
	ll res = 0;
	memset(h, 0, sizeof(h));

	while (f > 0) {
		priority_queue<pii, vector<pii>, greater<pii> > que;
		fill(dst, dst + N + 1, INF);
		dst[s] = 0;
		que.push(mp(0, s));
		while (!que.empty()) {
			pii p = que.top(); que.pop();
			int v = p.se;
			if (dst[v] < p.fi) continue;
			rep(i, g[v].size()) {
				edge &e = g[v][i];
				ll nd = dst[v] + e.cost + h[v] - h[e.to];
				if (e.cap > 0 && dst[e.to] > nd) {
					dst[e.to] = nd;
					prevv[e.to] = v;
					preve[e.to] = i;
					que.push(mp(dst[e.to], e.to));
				}
			}
		}

		if (dst[t] == INF) return -1;
		rep(i, N) h[i] += dst[i];

		int d = f;
		for (int v = t; v != s; v = prevv[v]) {
			d = min(d, g[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d * h[t];
		for (int v = t; v != s; v = prevv[v]) {
			edge &e = g[prevv[v]][preve[v]];
			e.cap -= d;
			g[v][e.rev].cap += d;
		}
	}

	return res;
}

const int tx[4] = {1, 1, -1, -1};
const int ty[4] = {1, -1, 1, -1};

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

	int num = 0;
	int s = 0;

	rep(i, n) {
		int x, y, c; cin >> x >> y >> c;
		add_edge(s, i + 1, c, 0ll);
		rep(d, 4) {
			add_edge(i + 1, n + 1 + d, 1e9, x * tx[d] + y * ty[d]);
		}

		num += c;
	}

	int t = 1 + n + 4 + n;
	N = n * 2 + 6;

	rep(i, n) {
		int x, y, c; cin >> x >> y >> c;
		add_edge(1 + n + 4 + i, t, c, 0ll);
		rep(d, 4) {
			add_edge(n + 1 + d, 1 + n + 4 + i, 1e9, x * tx[3-d] + y * ty[3-d]);
		}		
	}

	ll ans = min_cost_flow(s, t, num);
	cout << -ans << endl;

	return 0;
}

Measured memory_bytes: 34788
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
using i64 = long long;

int main()
{
  i64 n;
  cin >> n;
  vector<i64> h(n);
  for (i64 i = 0; i < n; i++)
    cin >> h[i];
  i64 ans = 0, now = 0;
  for (i64 i = 0; i < n; i++)
  {
    if (now <= h[i])
      ans++;
    now = max(now, h[i]);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
// F - Many Slimes
#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
	ios::sync_with_stdio(false); cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(1 << n);
	for (int i = 0; i < (1 << n); i++) cin >> a[i];
	multiset<int, greater<int> > s, t;
	for (int i = 0; i < a.size(); i++) s.insert(a[i]);
	t.insert(*s.begin());
	s.erase(s.begin());
	bool ok = true;
	for (int k = 0; k < n && ok; k++) {
		vector<int> c;
		for (multiset<int, greater<int> >::iterator it = t.begin(); it != t.end(); ++it) {
			multiset<int, greater<int> >::iterator it2 = s.upper_bound(*it);
			if (it2 == s.end() || *it2 == *it) {
				ok = false;
				break;
			}
			c.push_back(*it2);
			s.erase(it2);
		}
		for (int i = 0; i < c.size(); i++) t.insert(c[i]);
	}
	cout << (ok ? "Yes" : "No") << endl;

	return 0;
}


Measured memory_bytes: 15360
namespace VainZero.Procon.FSharp

open System
open System.Collections.Generic

[<AutoOpen>]
module Operators =
  let read f = Console.ReadLine().Split([|' '|]) |> Array.map f

module Program =
  [<EntryPoint>]
  let main _ =
    let [|r; g; b|] = read int
    let calc () =
      let n = r * 100 + g * 10 + b
      n % 4 = 0
    printfn "%s" (if calc () then "YES" else "NO")
    0


Measured memory_bytes: 11996
#include <iostream>
#include <list>
#include <string>
#include <stdio.h>
#include <stdint.h>
using namespace std;
using uint = unsigned int;
using int64 = int64_t;
using uint64 = uint64_t;

int main()
{

  string S;
  string T;

  cin >> S;
  cin >> T;
  cin.ignore();


  uint L = S.size();

  if( T.size() != L ){

    cout << "No" << endl;
    return 0;

  }

  for( uint i = 0 ; i < L ; i++ ){

    for( uint j = 0 ; i+j < L ; j++ ){

      if( S[i+j] != T[j] ){

	goto NEXT;

      }

    }

    for( uint j = 0 ; j < i ; j++ ){

      if( S[j] != T[L-i+j] ){

	goto NEXT;

      }

    }

    cout << "Yes" << endl;
    return 0;

  NEXT:
    ;

  }

  cout << "No" << endl;  
  return 0;
  
}


Measured memory_bytes: 256
N = int(input())
ans = N
for n9 in range(N//9+1):
    a = N - 9*n9
    if a < 0:
        continue
    c = 0
    while a >= 6:
        c += a % 6
        a = a // 6
    c2 = 0
    while n9 >= 9:
        c2 += n9 % 9
        n9 = n9 // 9
    cost = a + c + c2 + n9
    ans = min(ans, cost)
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <math.h>
#include <algorithm>
#include <map>
#include <sstream>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <functional>
#include <utility>
#include <stdio.h>
#define ll long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define F first
#define S second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
int n;
int a[100010],res[100010];
int main()
{
	cin >>n;
	for (int i=0;i<n;i++) cin >>a[i];
	res[0]=0;
	for (int i=1;i<n;i++)
	{
		if (a[i-1]>=a[i]) res[i]=res[i-1]+1;
		else res[i]=0;
	}
	cout <<*max_element(res,res+n);
	return 0;
}

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

#define ll long long
#define p_q priority_queue
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define MAX 1000000001


int main(){
    ll l,r;
    cin>>l>>r;

    ll len = r-l+1;

    if(len>=2019){
        cout<<0<<endl;
    }else{
        ll value=99999999999;
        for(ll i=l;i<=r;i++){
            for(ll j=i+1;j<=r;j++){
                value = min(value,((i%2019)*(j%2019))%2019);
            }
        }
        cout<<value<<endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <queue>
#include <cmath>

using namespace std;
using ll = long long;


void Students1D()
{
	int N;
	cin >> N;

	vector<int> v(N);
	for (int i = 1; i < N; ++i)
	{
		int ct = 1;
		int j = i;
		while (j % 2 == 0)
		{
			j /= 2;
			++ct;
		}
		v[i] = ct;
	}
	for (int i = N-1; i > 0; --i)
	{
		for (int j = 0; j < i; ++j)
		{
			cout << v[j+1];
			cout << ' ';
		}
		cout << endl;
	}
}

int main()
{
	Students1D();
	return 0;
}

Measured memory_bytes: 512
import Data.Functor( (<$>))

main = do
    formulas <- (takeWhile (\[_,op_,_]->op_/="?")) . (words <$>) . lines <$> getContents
    let
	calc [a,"+",b] = read a+read b
	calc [a,"-",b] = read a-read b
	calc [a,"*",b] = read a*read b
	calc [a,"/",b] = read a`quot`read b

    (print . calc) `mapM_` formulas



Measured memory_bytes: 4024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 100005, inf = 1e18;

ll n, a[N], dt[N][3];

int main()
{
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) {
		char T[2];
		if(i>1) scanf("%s",T);
		scanf("%lld",&a[i]);
		if(i>1 && T[0] == '-') a[i] *= -1;
	}
	dt[1][0] = a[1];
	dt[1][1] = dt[1][2] = -inf;
	for(ll i=2;i<=n;i++) {
		dt[i][0] = dt[i-1][0] + a[i];
		dt[i][2] = dt[i-1][2] + a[i];
		dt[i][1] = max(dt[i][2], dt[i-1][1] - a[i]);
		if(a[i] < 0) {
			dt[i][2] = max(dt[i][1], dt[i][2]);
			dt[i][1] = max(dt[i][0], dt[i][1]);
		}
	}
	printf("%lld\n",max({dt[n][0], dt[n][1], dt[n][2]}));
}


Measured memory_bytes: 3328
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
    int n,m;
	cin>>n>>m;
	long long a[n][2], b[m][2];
	for(int i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1];
	} 
	for(int i=0;i<m;i++){
		cin>>b[i][0]>>b[i][1];
	}
	int ans[51]={0};
	for(int i=0;i<n;i++){
		long long t=1e9;
		for(int j=0;j<m;j++){
			long long tt=abs(a[i][0]-b[j][0])+abs(a[i][1]-b[j][1]);
			if(t>tt){
				ans[i]=j;
				t=tt;
			}
		}
	}
	for(int i=0;i<n;i++){
		cout<<ans[i]+1<<endl;
	}
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int N;
int b[100];
#define rep(v,n) for(int v=0;v<n;v++)
#define REP(i, n) rep(i,n)

#define EXIST(c, a) c.find(a)!=c.end()

typedef long long ll;

int main(){
	map<char, char> mp[2];
	mp[0]['A']='X';
	mp[1]['A']='Y';
	mp[1]['X']='Z';
	mp[0]['Y']='X';
	mp[0]['Z']='W';
	mp[1]['Z']='B';
	mp[0]['W']='B';
	mp[1]['W']='Y';
	mp[0]['B']='Y';
	mp[1]['B']='X';
	
	while(true){
		char str[120];
		scanf("%s", str);
		if(str[0]=='#') break;
		int len = strlen(str);
		char now='A';
		REP(i, len){
			int x = str[i]-'0';
			if(EXIST(mp[x], now)){
				now = mp[x][now];
			}else now = '*';
		//	printf("%c ", now);
		}
		if(now=='B') printf("Yes\n");
		else printf("No\n");
	}
}

Measured memory_bytes: 1144
nmax = (10**6+1)*2
mod = 10**9+7

fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    for i in range(2,nmax):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) %mod
        finv[i] = finv[i-1] * inv[i] %mod

def ncr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n]* (finv[r] * finv[n-r] %mod) %mod

def g(r,c):## r以下かつc以下の経路f(i,j)の総和
    ans = 0
    for i in range(1,r+2):
        ## f(i+1,c) =  f(i,0) + f(i,1) + ...f(i,c)
        ans += ncr(i+c,c)
        ans %=mod
    return ans

ncr_pre()
r1,c1,r2,c2 = map(int,input().split())
ans = g(r2,c2) - g(r1-1,c2) - g(r2,c1-1) + g(r1-1,c1-1)
print(ans % mod)


Measured memory_bytes: 86000
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <tuple>

using namespace std;

class Solver {
};

int main() {
	while (true) {
		int n, m, t, p;
		cin >> n >> m >> t >> p;
		if (n == 0)break;

		vector<vector<int>> grid(m, vector<int>(n, 1));
		int left = 0;
		int down = 0;
		for (int i = 0; i < t; i++) {
			int d, c;
			cin >> d >> c;
			if (d == 1) {
				if (n - left - c < c) {
					for (int j = 0; left + j < n - 1 - j; j++) {
						for (int k = 0; k < m; k++) {
							int tmp = grid[k][left + j];
							grid[k][left + j] = grid[k][n - 1 - j];
							grid[k][n - 1 - j] = tmp;
						}
					}
					c = n - left - c;
				}

				for (int j = 0; j < c; j++) {
					int target = left + c * 2 - 1 - j;
					for (int k = 0; k < m; k++) {
						grid[k][target] += grid[k][left + j];
					}
				}
				left += c;
			}
			else {
				if (m - down - c < c) {
					for (int j = 0; down+j < m - 1 - j; j++) {
						for (int k = 0; k < n; k++) {
							int tmp = grid[down + j][k];
							grid[down + j][k] = grid[m - 1 - j][k];
							grid[m - 1 - j][k] = tmp;
						}
					}
					c = m - down - c;
				}

				for (int j = 0; j < c; j++) {
					int target = down + c * 2 - 1 - j;
					for (int k = 0; k < n; k++) {
						grid[target][k] += grid[down + j][k];
					}
				}
				down += c;
			}
		}

		for (int i = 0; i < p; i++) {
			int x, y;
			cin >> x >> y;
			cout << grid[down + y][left + x] << endl;
		}
	}
}


Measured memory_bytes: 3072
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;

int main(){
	int n;
	cin>>n;
	//k*(k-1)/2=n
	for(int k = 2;k < 1000;k ++){
		if(k*(k-1)/2==n){
			printf("Yes\n%d\n",k);
			int a[k][k];
			int counter=1;
			for(int i = 0;i < k;i ++){
				for(int j = 0;j < k;j ++){
					a[i][j]=0;
				}
			}
			for(int i = 0;i < k-1;i ++){
				for(int j = 0;j < k-i-1;j ++){
					a[i][j]=counter;
					counter++;
				}
			}
			for(int i = 0;i < k-1;i ++){
				printf("%d",k-1);
				for(int j = 0;j < k-i-1;j ++){
					printf(" %d",a[i][j]);
				}
				for(int j = 0;j < i;j ++){
					printf(" %d",a[j][k-i-2]);
				}
				printf("\n");
			}
			printf("%d",k-1);
			for(int i = 0;i < k-1;i ++){
				printf(" %d",a[i][k-i-2]);
			}
			printf("\n");
			return 0;
		}
	}
	printf("No\n");
	return 0;
}
/*
k=5
4, 7, 9, 10
k(k-1)/2-(k-j)*(k-1-j)/2


k=6
5, 9, 12, 14, 15


*/


Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll k;
	cin>>k;
	priority_queue<ll,vector<ll>,greater<ll> > pq;
	for(ll i=1;i<=9;i++)
		pq.push(i);
	ll c=0;
	while(!pq.empty())
	{
		ll x=pq.top();
		pq.pop();
		c++;
		if(c==k)
		{
			cout<<x<<"\n";
			return 0;
		}
		ll z=x%10;
		ll t=x*10+z;
		pq.push(t);
		if(z)
		{
			z--;
			pq.push(x*10+z);
			z++;
		}
		if(z+1<=9)
		{
			pq.push(x*10+z+1);
		}
	}
	return 0;
}

Measured memory_bytes: 2420
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

#define ONLINE_JUDGE
//#define int long long
const int MAXN = 1;
const int INF = 2e9;
const int mod = 1e9 + 7;

int x,y;

template<typename T> inline void read(T &a) {
	a = 0; char c = getchar(); int f = 1;
	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
	while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
	a *= f;
}

signed main () {
#ifndef ONLINE_JUDGE
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	read(x); read(y);
	puts((y % 2 == 0 && 2 * x <= y && y <= 4 * x) ? "Yes":"No");
	return 0;
}


Measured memory_bytes: 3620
import sys
import math
import itertools
import collections
from collections import deque
 
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
 
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
 
def main():
    A, B = NMI()
    GCD = math.gcd(A, B)
    N=GCD
    
    cnt = 0
    
    ls=[]
    
    for n in range(2,int(N**0.5)+2):
 
        if GCD % n == 0:
            cnt += 1
 
            while GCD % n == 0:
                GCD = GCD//n
                ls.append(n)
        
    if GCD == 1:
        print(cnt+1)
    else:
        print(cnt+2) 

if __name__ == '__main__':
    main()

Measured memory_bytes: 9664
n = int(input())
flower_list = [ int(v) for v in input().split() ]

def water():
    grown = 0
    l = 0
    r = n
    for i, v in enumerate(flower_list):
        if grown == 0:
            if v > 0:
                grown = 1
                l = i
        elif grown == 1:
            if v == 0:
                grown = 2
                r = i
    if grown != 0:
        for i in range(l,r):
            flower_list[i] -= 1

    flg = 0
    if grown == 0:
        flg = 1
    return flg

ans = 0
stop = 0
while stop == 0:
    stop = water()
    if stop == 0:
        ans += 1

print(ans)


Measured memory_bytes: 41324
from time import time
import random


def main():
    random.seed(145)

    start = time()

    MAX = 26

    d = int(input())
    c = list(map(int, input().split()))
    s = [list(map(int, input().split())) for _ in range(d)]

    t = []
    prev = [0] * MAX
    for day, row in enumerate(s, 1):
        mxi = 1
        mx = 0
        for i, (es, ec) in enumerate(zip(row, c), 1):
            point = es + ec * (day - prev[i-1])
            if point > mx:
                mx = point
                mxi = i

        prev[mxi-1] = day
        t.append(mxi)

    last = [0] * MAX

    score = 0
    for day, e in enumerate(t, 1):
        score += s[day-1][e-1]
        last[e-1] = day

        for ec, elast in zip(c, last):
            score -= ec * (day - elast)

    d_li = []
    for i in range(1, d + 1):
        ln = max(1, (-(i - d // 2) ** 2 + d ** 2 // 4) // 500)
        d_li += [i] * ln

    di_max = len(d_li) - 1

    #c_sum = sum(c)
    #c_li = []
    #for i, e in enumerate(c, 1):
    #    c_li += [i] * e

    sc = []
    for row in s:
        app = []
        for i, (es, ec) in enumerate(zip(row, c), 1):
            app += [i] * max(1, (es + ec * d) // 20)
        sc.append(app)

    now = time()

    cnt = 0
    no_change = 0
    while now - start <= 1.85:
        prev_score = score
        cnt += 1

        di = random.randint(0, di_max)
        ed = d_li[di]
        qi = random.randint(0, len(sc[ed-1]) - 1)
        eq = sc[ed-1][qi]

        q_old = t[ed-1]
        d_prev = {q_old: 0, eq: 0}

        c_old = c[q_old-1]
        c_new = c[eq-1]

        for day, e in enumerate(t, 1):
            if e in d_prev.keys():
                d_prev[e] = day

            score += c_old * (day - d_prev[q_old])
            score += c_new * (day - d_prev[eq])

        score -= s[ed-1][q_old-1]
        score += s[ed-1][eq-1]

        t[ed-1] = eq

        d_prev = {q_old: 0, eq: 0}

        for day, e in enumerate(t, 1):
            if e in d_prev.keys():
                d_prev[e] = day

            score -= c_old * (day - d_prev[q_old])
            score -= c_new * (day - d_prev[eq])

        now = time()

        if prev_score < score or random.randint(1, int((now - start) * 1000)) <= 500:
            continue

        no_change += 1
        t[ed-1] = q_old
        score = prev_score

    print(*t, sep="\n")
    #print(cnt, no_change)


if __name__ == "__main__":
    main()


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

using namespace std;

int n;
int a[200001];
long long gao(int x) { return 1LL * x * (x - 1) / 2; }
long long ans = 0;
int cnt[200001];
int main( ) {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i ++) {
		
		ans -= gao(cnt[a[i]]);
		cnt[a[i]] ++; 
		ans += gao(cnt[a[i]]);
	}
	for (int i = 1; i <= n; i ++) {
		ans -= gao(cnt[a[i]]);
		cnt[a[i]] --;
		ans += gao(cnt[a[i]]);
		printf("%lld\n", ans);
		ans -= gao(cnt[a[i]]);
		cnt[a[i]] ++;
		ans += gao(cnt[a[i]]);
	}
	return 0;
}



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

using namespace std;
using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string S;
  cin >> S;
  ll res = 0;
  for (int i = 0; i < (1 << ((int)S.size() - 1)); i++) {
    ll tmp = S[0] - '0';
    for (int j = 0; j < ((int)S.size() - 1); j++) {
      if ((i >> j) & 1) {
        res += tmp;
        tmp = 0;
      }
      tmp *= 10;
      tmp += S[j + 1] - '0';
    }
    res += tmp;
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????

		int[][] masu = new int[10][10];
		String input = "";
		int x = -1;
		int y = -1;
		int s = -1;
		int cnt = 0;
		int max = 0;

		for(int i = 0;i < 10;i++){
			for(int j = 0;j <10;j++){
				masu[i][j] = 0;
			}
		}

		try{

			while((input = br.readLine()) != null){
				String[] inputs = input.split(",");
				x = Integer.parseInt(inputs[0]);
				y = Integer.parseInt(inputs[1]);
				s = Integer.parseInt(inputs[2]);

				drop(masu,x,y,s);

			}

		}catch(Exception e){

		}

		for(int i = 0;i < 10;i++){
			for(int j = 0;j <10;j++){
				if(masu[i][j] == 0){
					cnt++;
				}
				if(max <= masu[i][j]){
					max = masu[i][j];
				}
			}
		}

		System.out.println(cnt + "\n" + max);

	}

	static void drop(int blocks[][],int x, int y, int size){
        if(size == 1)//?°??????´
            min_drop(blocks, x, y);
        if(size == 2)
            mid_drop(blocks, x, y);
        if(size == 3)
            lag_drop(blocks, x, y);
    }

    static void min_drop(int blocks[][], int x, int y){
        blocks[x][y]++;
        if(x-1>-1)
            blocks[x-1][y]++;
        if(x+1<10)
            blocks[x+1][y]++;
        if(y-1>-1)
            blocks[x][y-1]++;
        if(y+1<10)
            blocks[x][y+1]++;
    }

    static void mid_drop(int blocks[][], int x, int y){
        min_drop(blocks, x, y);
        if(-1<x-1 && -1<y-1)
            blocks[x-1][y-1]++;
        if(x+1<10 && -1<y-1)
            blocks[x+1][y-1]++;
        if(-1<x-1 && y+1<10)
            blocks[x-1][y+1]++;
        if(x+1<10 && y+1<10)
            blocks[x+1][y+1]++;
    }

    static void lag_drop(int blocks[][], int x, int y){
        mid_drop(blocks, x, y);
        if(-1<y-2)
            blocks[x][y-2]++;
        if(y+2<10)
            blocks[x][y+2]++;
        if(-1<x-2)
            blocks[x-2][y]++;
        if(x+2<10)
            blocks[x+2][y]++;
    }

}

Measured memory_bytes: 24272
n = int(input())
A = list(map(int,input().split()))

print(' '.join(map(str,A)))

for i in range(1,n):
    v = A[i]
    j = i-1
    while j>=0 and v < A[j]:
        A[j+1] = A[j]
        j -= 1
        A[j+1] = v
    print(' '.join(map(str,A)))


Measured memory_bytes: 5596