akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
int main() {
	int n;
	cin >> n;
	vector<int> x(n);
	
	for (int i = 0; i < n; i++) {
		cin >> x[i];
	}
    int l = x[0];
    int r = x[0];

    for (int i = 1; i < n; i++){
    	l = min(l, x[i]);
        r = max(r, x[i]);
    }
    int ans = inf;
    for (int i = l; i <= r; i++) {
    	int cost = 0;
    	for (int j = 0; j < n; j++){
    		cost += pow(x[j] - i, 2);
    	}
    	ans = min(ans, cost);
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n, a, b, p = 0;
    cin >> n;
    cin >> a;
    p += a / 2;
    b = a % 2;

    for(int i = 1; i < n; i++){
        cin >> a;
        p += (a + b) / 2;
        if(a == 0) b = 0;
        else b = (a + b) % 2;
    }

    cout << p;

    return 0;
}


Measured memory_bytes: 256
def answer():
    N = int(input())
    As = list(map(int, input().split()))

    total = sum(As)
    half = total//2

    sum_left = 0
    sum_left2 = 0
    idx = 0

    for i, l in enumerate(As[:-1]):
        sum_left += l
        if sum_left >= half:
            idx = i
            sum_left2 = sum_left - l
            break

    sum_right = sum(As[idx+1:])
    sum_right2 = sum(As[idx:])

    ans1 = abs(sum_right - sum_left)
    ans2 = abs(sum_right2 - sum_left2)

    print(min(ans1, ans2))


if __name__ == '__main__':
    answer()


Measured memory_bytes: 26220
import math
from collections import defaultdict
from itertools import product
from functools import reduce 
from operator import mul


def is_prime(num):
    if not isinstance(num, int):
        return False
    if num <= 1:
        return False
    if num == 2 or num == 3:
        return True
    if num % 6 in [0, 2, 3, 4]:
        return False
    div_max = int(math.sqrt(num))
    for div in range(5, div_max + 1, 2):
        if num % div == 0:
            return False
    return True

def factorint(x):
    factors = defaultdict(int)
    if x==1:
        factors[1] = 1
        return factors
    while not is_prime(x):
        div_max = int(math.sqrt(x))
        for div in range(2, div_max + 1):
            if x % div == 0:
                factors[div] += 1
                x = int(x / div)
                break
    factors[x] += 1
    return factors

ans = 0
n = int(input())
rn = math.sqrt(n+1) + 1
factor_dict = factorint(n)
ks = [range(k+1) for k in factor_dict.values()]
prs = product(*ks)
for pr in prs:
    s = reduce(mul, [factor**p for factor,p in zip(factor_dict.keys(), pr)])
    if s >= rn:
        ans += s -1
print(ans)


Measured memory_bytes: 3696
#include <bits/stdc++.h>
using namespace std;
int abso(int x)
{
    return x>0?x:(-1*x);
}
int main()
{
    int i,n;
    cin>>n;
    int h[n+1];
    for(i=1;i<=n;i++)
        cin>>h[i];
    int ans[n+1];
    ans[1]=0;
    ans[2]=abso(h[2]-h[1]);
    for(i=3;i<=n;i++)
        ans[i]=min(ans[i-1]+abso(h[i]-h[i-1]),ans[i-2]+abso(h[i]-h[i-2]));
    cout<<ans[n]<<endl;
}


Measured memory_bytes: 1024
lucas = {}

def luca(i):
    global lucas
    if i in lucas:
        return lucas[i]
    elif i == 0:
        ret = 2
    elif i == 1:
        ret = 1
    else:
        ret = luca(i-2) + luca(i-1)
    lucas[i] = ret
    return ret

N = int(input())

print(luca(N))


Measured memory_bytes: 3316
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct stype {
   char s[11];
};

struct ctype {
   int i,c;
};

int ass(const void *a, const void *b) {
  return strcmp((*(struct stype *)a).s,(*(struct stype *)b).s);
}

int asc(const void *a, const void *b) {
  return (*(struct ctype *)b).c - (*(struct ctype *)a).c;
}

int main(){
   int i,n,j,m,mm;
   struct stype ss[200000];
   struct ctype cc[200000];
 
   scanf("%d",&n);
   for (i=0;i<n;i++) scanf("%s",ss[i].s);
   qsort(ss,n,sizeof(struct stype),ass);
   m=0;mm=0;
   for (i=0;i<n;i++) {
      for (j=i+1;j<n;j++)
         if (strcmp(ss[i].s,ss[j].s)!=0) break;
      if (j-i>mm) {
         mm=j-i;
         m=0;
      } 
      if (j-i==mm) {
         cc[m].i=i;
         m++;
      }
      i=j-1;
   }
   for (i=0;i<m;i++) printf("%s\n",ss[cc[i].i].s);
   return 0;
}


Measured memory_bytes: 5884
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;

const int INF = 1<<29;

int main(){
    int n, m; cin >> n >> m;
    vector<int> a(m), b(m), c(m);
    vector<vector<int>> dist(n, vector<int>(n,INF));
    rep(i,n) dist[i][i] = 0;
    rep(i,m){
        cin >> a[i] >> b[i] >> c[i];
        --a[i], --b[i];
        dist[a[i]][b[i]] = c[i];
        dist[b[i]][a[i]] = c[i];
    }
    for(int k = 0; k < n; ++k){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    int res = 0;
    //全ての辺について、全ての頂点間の最短経路を調べ、一回でも含まれていたらTrue
    rep(i,m){
        bool ok = false;
        rep(p,n)rep(q,n){
            if(dist[p][q] == dist[p][a[i]]+c[i]+dist[b[i]][q]) ok = true;
        }
        if(!ok) res++;
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define mem(a,k) memset(a,k,sizeof(a))
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using namespace std;

#define Pr(f,...) fprintf(stderr,f,##__VA_ARGS__),fflush(stderr)

typedef long long ll;

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

const int N=1e5+5,P=998244353;

int mul(int a,int b){ return 1ll*a*b%P; }
int add(int a,int b){ a+=b; return a>=P?a-P:a; }
int sub(int a,int b){ a-=b; return a<0?a+P:a; }
int gcd(int a,int b){ return !b?a:gcd(b,a%b); }

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
#endif
	int x;
	cin>>x; 
	cout<<360/gcd(x,360)<<endl;
	return 0;
}


Measured memory_bytes: 3588
/*
 Shahadat Hossain
 I.C.T Department
 Comilla University
 Session: 2013-2014
 */

#include<iostream>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<cstring>

using namespace std;

int const N = 1e6 + 5;
int const MOD = 1e9 + 7;

int ar[N];
int l[N], r[N];

int main(){
    
    int n;
    cin >> n;
    
    int mx = 0;
    for(int i = 1; i <= n; i++){
        cin >> ar[i];
        mx = max(ar[i], mx);
        l[i] = mx;
    }
    
    mx = 0;
    for(int i = n; i >= 1; i--){
        mx = max(ar[i], mx);
        r[i] = mx;
    }
    
    for(int i = 1; i <= n; i++){
        cout << max(l[i - 1], r[i + 1]) << endl;
    }
    
}


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

int main()
{
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	int left=a+b;
	int right=c+d;
	if(left>right)
		cout<<"Left"<<endl;
	else if(left==right)
		cout<<"Balanced"<<endl;
	else
		cout<<"Right"<<endl;
	return 0;
}

Measured memory_bytes: 256
H,W = [int(i) for i in input().split()]
maze = [list(input()) for _ in range(H)]
dica = [[-1] * W for _ in range(H)]
import collections
from collections import deque
import numpy as np
dx = [1,0,-1,0]
dy = [0,1,0,-1]
ans = -1
for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            dic = [k[:] for k in dica]
            que = deque()
            que.append([i,j])
            dic[i][j] = 0
            while len(que) != 0:
                k = que.popleft()
                x = k[0]
                y = k[1]
                for l in range(4):
                    nx = x + dx[l]
                    ny = y + dy[l]
                    if nx < 0 or ny < 0 or nx >= H or ny >= W:
                        continue
                    if maze[nx][ny] == "#":
                        continue
                    if dic[nx][ny] != -1:
                        continue
                    dic[nx][ny] = dic[x][y] + 1
                    que.append([nx,ny])
            arr = np.array(dic)
            M = np.amax(arr)
            if M > ans:
                ans = M
print(ans)

Measured memory_bytes: 14360
#include <bits/stdc++.h>
 
using namespace std;
 
#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; scanf("%lld", &x);
#define int2(x, y) int x, y; scanf("%lld %lld", &x, &y);
 
//int dxy[5] = {0, 1, 0, -1, 0};
// assign
 
signed main()
{
    int n;
    string input;
    cin >> n >> input;
    string state[4];
    char st[4];

    if (input[0] == 'o') {
        state[0] = "SS";
        st[0] = 'S';
        state[1] = "SW";
        st[1] = 'W';
        state[2] = "WS";
        st[2] = 'W';
        state[3] = "WW";
        st[3] = 'S';
    } else {
        state[0] = "SS";
        st[0] = 'W';
        state[1] = "SW";
        st[1] = 'S';
        state[2] = "WW";
        st[2] = 'W';
        state[3] = "WS";
        st[3] = 'S';
    }

    Rep(i, n) {
        rep(j, 4) {
            if (state[j][i] == 'S') {
                if (input[i] == 'o') {
                    state[j].pb(state[j][i-1]);
                } else {
                    state[j].pb((state[j][i-1] == 'S') ? 'W' : 'S');
                }
            } else {
                if (input[i] == 'o') {
                    state[j].pb((state[j][i-1] == 'S') ? 'W' : 'S');
                } else {
                    state[j].pb(state[j][i-1]);
                }
            }
        }
    }
//    rep(i, 4) cout << state[i] << endl;

    int ans = -1;
    rep(i, 4) {
        if (state[i][n-1] == st[i] && state[i][0] == state[i][n]) {
            ans = i;
        }
    }
    if (ans != -1) {
        rep(i, state[ans].length()-1) {
            cout << state[ans][i];
        }
        cout << endl;
    } else {
        cout << ans << endl;
    }


    return 0;
}



Measured memory_bytes: 1152
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include <iomanip>
typedef long long int ll;
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) for (int i=0;i<(n);i++)
#define EREP(i,n) for (int i=1;i<=(n);i++)
#define ALL(a) (a).begin(),(a).end()
//#define EVEL 1

#ifndef EVEL
#define DEB(X) cout << #X << ":" <<X<<" " ;
#define TF(f) f ? cout<<"true  " : cout<<"false ";
#define END cout<<"\n";
#else
#define DEB(X) {X=X;}
#define TF(f) {f=f;}
#define END {}
#endif
const int MOD = 1000000007;
const int INF = 1000000;
#define NMAX 50
#define MAX 10

    ll N,M,A,B;
    ll temp=0,id=0,mem,yui=1,sum=0;
    ll x[100010],y[100010];
    ll w,h;
    bool fir=true;



int main(){
    ios_base::sync_with_stdio(false);
    cin>>N>>M;
    if((abs(N-M))<=1){
        cout<<"Brown";
    }else{
        cout<<"Alice";
    }
}
//ABC059 Alice&Brown


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int min;
	int now;
	int max;
	char train[4000];
	char input[2000];
	int datamax;
	int datanum;
	int i;
	scanf("%d",&datamax);
	while(getchar()!='\n');
	for(datanum=0;datanum<datamax;datanum++) {
		fgets(input,sizeof(input),stdin);
		now=2000;
		min=2000;
		max=2000;
		for(i=0;;i+=3) {
			train[now]=input[i];
			if(input[i+1]==0 || input[i+1]=='\n')break;
			if(input[i+1]=='-')now++; else now--;
			if(now<min)min=now;
			if(now>max)max=now;
		}
		for(i=min;i<=max;i++)putchar(train[i]);
		puts("");
	}
	return 0;
}

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

int ds(int d){
   if(d < 10)  return d;
   return ds(d/10) + d%10;
}

int main(){
    int n;
    cin>>n;
    int ans=1e9;
    for(int i=1; i<n; ++i){
        int x=n-i;
    ans=min(ans,ds(i)+ds(x));
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
    int n;
    string s;
    cin >> n;
    if(n == 0){
        cout << 0 << "\n";
        return 0;
    }
    while (n){
        if (n & 1) {s.insert(0, "1"); n = (n-1)/-2;}
        else {s.insert(0, "0"); n /= -2;}
    }
    cout << s << "\n";
    return 0;
}


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

int main() {
    long long int n,x;
    cin>>n>>x;
    long long int l[n],d[n+1];
    for(int i=0;i<n;i++)
    cin>>l[i];
    d[0]=0;
    for(long long int i=1;i<n+1;i++)
    d[i]=d[i-1]+l[i-1];
    
    long long int k=0;
    for(long long int i=0;i<n+1;i++)
    {
        if(d[i]<=x)
        k++;
    }
    
    cout<<k;
	return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Sun May  3 21:27:48 2020
"""

import sys
import numpy as np
import itertools

sys.setrecursionlimit(10 ** 9)

N = int(input())
A = np.array(list(map(int,input().split())))
B = np.arange(N)
x = B - A
y = B + A

x = x[x>0]
y = y[y<N]
x_count = np.bincount(x, minlength = N)
y_count = np.bincount(y, minlength = N)

ans = np.sum(x_count * y_count)

print(ans)

Measured memory_bytes: 50904
//15
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
  int n;
  cin>>n;
  while(n--){
    int t[128],b[128]={},l[128],r[128]={};
    fill(t,t+128,100);
    fill(l,l+128,100);
    int h,w;
    cin>>h>>w;
    char g[50][50];
    for(int y=0;y<h;y++){
      for(int x=0;x<w;x++){
	char c;
	cin>>c;
	g[y][x]=c;
	t[c]=min(t[c],y);
	b[c]=max(b[c],y);
	l[c]=min(l[c],x);
	r[c]=max(r[c],x);
      }
    }
    bool safe=true;
    int d[128][128];
    fill(d[0],d[128],1<<29);
    for(char c='A';c<='Z';c++){
      for(int y=t[c];y<=b[c];y++){
	for(int x=l[c];x<=r[c];x++){
	  if(g[y][x]=='.'){
	    safe=false;
	  }else{
	    d[c][g[y][x]]=((c==g[y][x])?0:-1);
	  }
	}
      }
    }
    for(char i='A';i<='Z';i++){
      for(char j='A';j<='Z';j++){
	for(char k='A';k<='Z';k++){
	  d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
	}
      }
    }
    for(char i='A';i<='Z';i++){
      if(d[i][i]<0){
	safe=false;
      }
    }
    cout<<(safe?"SAFE":"SUSPICIOUS")<<endl;
  }
  return 0;
}

Measured memory_bytes: 1220
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pa;
typedef unsigned int uint;
typedef unsigned long long ull;
int main() {
	char a;
	cin >> a;
	if (a >= 97)cout << "a" << endl;
	else cout << "A" << endl;



	return 0;
}

Measured memory_bytes: 3584
import java.util.Scanner;

public class Main {

  /*
     input:
         3 2
         2 2
         5 3
         0 0
     output:
         2 3
         2 2
         3 5
  */
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int x, y;

    while (true) {
      x = scan.nextInt();
      y = scan.nextInt();
      if (x + y == 0) break;
      System.out.printf("%d %d\n", Math.min(x, y), Math.max(x, y));
    }
  }
}


Measured memory_bytes: 39748
#include <bits/stdc++.h>
 
using namespace std;
 
int H, W, C, ans, cnt;
const int dx[] = {-1,0,0,1};
const int dy[] = {0,-1,1,0};
bool used[8][8];
typedef pair<int,int> P;
 
bool inField(int y, int x){
    return 0 <= y && y < H && 0 <= x && x < W;
}
 
void color_count(vector<vector<int> > &vec, int y, int x){
    if(used[y][x]) return;
    used[y][x] = true;
    if(vec[y][x] == C){
	cnt++;
    }
    for(int i = 0 ; i < 4 ; i++){
	int nx = x + dx[i];
	int ny = y + dy[i];
	if(!inField(ny, nx)) continue;
	if(vec[ny][nx] != C) continue;
	color_count(vec, ny, nx);
    }
}
 
vector<P> pos;
void color_change(int y, int x, int c1, int c2, 
                  bool flg, vector<vector<int> > &vec){
    if(used[y][x]) return;
    used[y][x] = true;
    pos.push_back(P(y,x));
    for(int i = 0 ; i < 4 ; i++){
	int nx = x + dx[i];
	int ny = y + dy[i];
	if(!inField(ny, nx)) continue;
	if(vec[ny][nx] != c1 && vec[ny][nx] != c2) continue;
	if(vec[y][x] != vec[ny][nx] && !flg){
	    flg = true;
	    color_change(ny, nx, c1, c2, flg, vec);
	}else{
	    if(flg){
		if(vec[y][x] != vec[ny][nx]) continue;
		color_change(ny, nx, c1, c2, flg, vec);
	    }else{
		color_change(ny, nx, c1, c2, flg, vec);
	    }
	}
    }
}
 
void solve(vector<vector<int> > &vec, int rem){
    if(rem == 0){
	memset(used, false, sizeof(used));
	cnt = 0;
	color_count(vec, 0, 0);
	ans = max(ans, cnt);
	return;
    }
   
    for(int i = 0 ; i < 6 ; i++){
	vector<vector<int> > next = vec;
	pos.clear();
	memset(used, false, sizeof(used));
	color_change(0, 0, i+1, vec[0][0], false, vec);
	for(int j = 0 ; j < pos.size() ; j++){
	    P p = pos[j];
	    next[p.first][p.second] = i+1;
	}
	solve(next, rem-1);
    }
}
 
int main(){
    while(cin >> H >> W >> C , (H | W | C)){
	vector<vector<int> > vec(H, vector<int>(W));
	for(int i = 0 ; i < H ; i++){
	    for(int j = 0 ; j < W ; j++){
		cin >> vec[i][j];
	    }
	}
	ans = 0;
	solve(vec, 5);   
	cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 3156
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <deque>

#define Inf             987654321
using namespace std;

typedef long long int   ll;
typedef pair<ll, ll>    pii;
typedef vector<ll>      vi;
typedef vector<vi>      vii;
typedef vector <vector<char> > vvc;
typedef vector <char> vc;
/*************************************************/

ll N, K, R, S, P, ans;
string T;

void sol() {
    for (ll i = 0; i < N; i++) {
        if (i >= K) {
            if (T[i] == T[i - K]) {
                T[i] = 'x';     //중복이므로 continue,
                continue;       //하지만 다음 K번째에는 영향을 주면 안되므로 'x'로 처리한다.
            }                   //가위바위보라서 선택지가 이기는것말고 2개이기 때문에 가능한 경우.
        }
        if (T[i] == 'r') ans += P;
        else if (T[i] == 's') ans += R;
        else if (T[i] == 'p') ans += S;
        else;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(); cout.tie();
    cin >> N >> K >> R >> S >> P >> T;
    sol();
    cout << ans;
    return 0;
}


Measured memory_bytes: 512
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();

		System.out.println(N*A > B ? B : N*A);
	}
}


Measured memory_bytes: 23124
/*

Coded and Decoded by : Yash Kapoor

*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

// s.find_by_order(index);
// s.order_of_key(value);

#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define mp make_pair
#define pll pair<ll, ll>
#define vl vector<ll>
#define sl set<ll>
#define vll vector<pll>
#define ml map<ll, ll>
#define mll map<pll, ll>
#define all(a) a.begin(), a.end()
#define x first
#define y second
#define sz(x) (ll) x.size()
#define dl '\n'
#define why (ll)1000000007
//#define why         (ll)998244353
#define lp(i, a, b) for (ll i = a; i < b; ++i)
#define lpr(i, a, b) for (ll i = a; i >= b; i--)
#define lpd(i, x) for (auto i : x)
#define ios                                                                                                            \
  ios_base::sync_with_stdio(false);                                                                                    \
  cin.tie(0);                                                                                                          \
  cout.tie(0);

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

ll inf = 1e18;
ld pi = 3.141592653589;
ll mod = why;
ll fast_power(ll base, ll power, ll mod)
{
  ll result = 1;
  while (power) {
    if (power % 2)
      result = (result * base) % mod;
    base = (base * base) % mod;
    power /= 2;
  }
  return result;
}

ll inverse(ll base, ll mod) { return fast_power(base, mod - 2, mod); }
int test = 1;
void solve() 
{
  ll n,w; cin >> n >> w;
  vll a(n);
  lp(i,0,n) cin >> a[i].x >> a[i].y;
  sort(all(a));
  ll dp[n+1][w+1];
  memset(dp, 0, sizeof dp);
  lp(i,1,n+1){
    lp(j,1,w+1){
      if(a[i - 1].x <= j){
        dp[i][j] = max(a[i-1].y + dp[i - 1][j - a[i - 1].x], dp[i - 1][j]);
      } else {
        dp[i][j] = dp[i-1][j];
      }
    }
  }
  cout << dp[n][w];
}

int main()
{
  // #ifndef ONLINE_JUDGE 
  //   freopen("input.txt", "r", stdin);
  //   freopen("output.txt", "w", stdout);
  // #endif
  ios 
  ll t = 1;
  //cin >> t;
  while (t--) 
  {
    //cout << "Case #" << test++ << ": ";
    solve();
  }
}

Measured memory_bytes: 82528
#include <bits/stdc++.h> //C++の標準ライブラリを一行で一括でインクルードする
#include <math.h> //数学関数と数学定数を利用する
#define rep(i,n) for (int i = 0; i < (n); i++)
#define PI 3.141592653589793
using namespace std;
typedef long long ll;
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}
ll gcd(ll a, ll b){//ユークリッドの互除法
  if (a < b) gcd(b,a); //aの方がbよりでかいのが前提
  if (b == 0) return a; //aをbで割り切れたらreturn
  else gcd(b, a % b);
}

ll lcm(ll a, ll b){
  ll g = gcd(a,b);
  ll ret;
  ret = a / g * b;
  return ret;
}
const int INF = 1<<30;
const int MOD = 1000000007;
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};

int func(int n){
  int ret = 0;
  while(n%2 == 0){
    n /= 2;
    ret++;
  }
  return ret;
}

int main(){
  int n,m; cin >> n >> m;
  vector<int> a(n);
  rep(i,n){
    cin >> a[i];
    a[i] /= 2;
  }
  
  ll t = func(a[0]);
  
  rep(i,n){
    if(func(a[i]) != t){
      cout << 0 << endl;
      return 0;
    }else{
      a[i] >>= t;
    }
  }
  
  m >>= t;
  
  ll l = 1;
  rep(i,n){
    l = lcm(l,a[i]);
    if(l > m){
      cout << 0 << endl;
      return 0;
    }
  }
  m /= l;
  ll ans = (m+1)/2;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
#include <cstdio>
using namespace std;

int a[4];
int c[8];
int k;

int calc(){
	int op = c[k++];
	int ret = 0;
	if(op >= 0){
		ret = op;
	}
	else if(op >= -3){
		int x = calc();
		int y = calc();
		if(op == -1){
			ret = x + y;
		}
		else if(op == -2){
			ret = x - y;
		}
		else{
			ret = x * y;
		}
	}
	else{
		throw 0;
	}
	return ret;
}

void print(){
	int op = c[k++];
	if(op >= 0){
		printf("%d", op);
	}
	else{
		char ch;
		if(op == -1){ ch = '+'; }
		else if(op == -2){ ch = '-'; }
		else{ ch = '*'; }

		putchar('(');
		print();
		printf(" %c ", ch);
		print();
		putchar(')');
	}
}

void solve(int i, int S){
	if(i == 7){
		try{
			if(S == 0){
				k = 0;
				if(calc() == 10 && k == 7){
					k = 0;
					print();
					puts("");
					throw "";
				}
			}
		}catch(int){}
		return;
	}

	for(int op = -1; op >= -3; --op){
		c[i] = op;
		solve(i + 1, S);
	}
	
	for(int j = 0; j < 4; ++j){
		if(S >> j & 1){
			c[i] = a[j];
			solve(i + 1, S ^ 1 << j);
		}
	}
}

int main(){
	while(1){
		for(int i = 0; i < 8; ++i){
			c[i] = -9;
		}
		for(int i = 0; i < 4; ++i){
			scanf("%d", &a[i]);
		}
		if(a[0] == 0){ break; }
		try{
			solve(0, 15);
			puts("0");
		}catch(...){}
	}
}

Measured memory_bytes: 1124
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String ans[] = {"Sunny", "Cloudy", "Rainy"};
		sc.close();
		int an = 0;
		for(int i = 0; i < 3; ++i){
			if(s.equals(ans[i])){
				an = i + 1;
				an %= 3;
				break;
			}
		}
		System.out.println(ans[an]);
	}
}


Measured memory_bytes: 20820
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
typedef long long ll;
const ll longinf=1LL<<60;
using namespace std;
char c;
char a[1000];
char b[1000];
int t1,t2;

bool check(int pos)
{
    for (int i=0; i<t2; ++i)
    {
        if (a[pos+i]==b[i] || a[pos+i]=='?')
            continue;
        return 0;
    }
    return 1;
}

void print(int pos)
{
    for (int i=0; i<pos; ++i)
        if (a[i]=='?') cout<<'a';
        else cout<<a[i];
    for (int i=0; i<t2; ++i)
        cout<<b[i];
    for (int i=pos+t2; i<t1; ++i)
        if (a[i]=='?') cout<<'a';
        else cout<<a[i];
    cout<<endl;
}


int main()
{
    while (1)
    {
        scanf("%c",&c);
        if (c=='\n') break;
        a[t1++]=c;
    }
    while (1)
    {
        scanf("%c",&c);
        if (c=='\n' || c==EOF) break;
        b[t2++]=c;
    }
    for (int i=t1-1; i>=0; --i)
        if (check(i))
        {
            print(i);
            return 0;
        }
    cout<<"UNRESTORABLE"<<endl;
    return 0;
}



Measured memory_bytes: 256
N, K = map(int, input().split())
h_list = [int(input()) for _ in range(N)]

h_list.sort(reverse=True)

sa = [0 for _ in range(N-K+1)]
for i in range(N-K+1):
    sa[i] = h_list[i] - h_list[i+K-1]

print(min(sa))

Measured memory_bytes: 11288
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007ll
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define pb push_back
#define mp make_pair
#define x first
#define y second
#define db(x) cout << #x << " = " << x << '\n'
#define sep cout << "********************************************\n"
#define fast ios_base::sync_with_stdio(false), cin.tie(NULL)
int main(int argc, char const *argv[])
{
	fast;
	ll a, b, c, k, s = 0;
	cin >> a >> b >> c >> k;
	ll mn = min(k, a);
	s += mn;
	k -= mn;
	mn = min(k, b);
	k -= mn;
	mn = min(k, c);
	s -= mn;
	cout << s;

	return 0;
}

Measured memory_bytes: 3648
import java.io.*;

class Main {
  public static void main(String[] args)throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String str = br.readLine();
    int S = Integer.parseInt(str);
    
    int h = (int)S/3600;
    int m = S%3600/60;
    int s = (S%3600)%60;
    
    System.out.println(h +":"+ m +":"+s);
    
  }
}

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

using namespace std;

int main() {
	int A, B,N;
	cin >> N;
	int count = 0;

	for (int a = 0; a <= 25; ++a) {
		for (int b = 0; b <= 15; ++b) {		
				if (N == 4 * a + 7 * b ) {
					count = count + 1;		
			}
		}
	}

	if (count > 0)cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef unsigned long long ll;


int main()
{
	int n;
	cin>>n;
	int ans = 0;
	for(int i = 1; i <= n; i = i + 2){
		int numOfDiviser = 0;
		for(int j = 1; j <= i; j++){
			if( i % j == 0) numOfDiviser++;
		}
		if(numOfDiviser == 8){
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}



Measured memory_bytes: 764
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

template <typename T>
using vec = vector<T>;

template <typename T>
using vec2 = vector<vector<T>>;

template <typename T>
using vec3 = vector<vector<vector<T>>>;

const Ld pi = M_PI;
const Int MOD = 1000000007;
const Int INF = 1LL << 61;

Int Floor(Int a, Int b) {
    return (a - (a % b)) / b;
}

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

    int g = 0, s = 0;
    for (int i = 0; i < 3; i++) {
        int a;
        cin >> a;

        if (a == 7) {
            s++;
        } else if (a == 5) {
            g++;
        }
    }

    if (g == 2 && s == 1) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(long long i = 0; i < n; i++)
#define REPR(i, n) for(long long i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(long long i = m; i <= n; i++)
#define FORR(i, m, n) for(long long i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
const ll mod = 1e9+7;



int main(){FIN

    ll m,k;cin>>m>>k;

    if(k >= pow(2,m)){
        cout<<-1<<endl;
        return 0;
    }

    else if (m==0) {
        cout<<0<<' '<<0<<endl; return 0;
    }
    else if(m==1 && k==0){
        cout<<0<<' '<<0<<' '<<1<<' '<<1<<endl; return 0;
    }



    else if(m>=2){
        FOR(i,0,pow(2,m)-1){
            if (i==k) continue;
            cout<<i<<' ';
        }
        cout<<k<<' ';
        FORR(i, pow(2,m)-1, 0){
            if (i==k)continue;
            cout<<i<<' ';
        }
        cout<<k<<endl;
        return 0;
    }

    cout<<-1<<endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <numeric>

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

using namespace std;


int main(){
    string s;
    cin >> s;
    if (s == "Sunny"){
        cout << "Cloudy" << endl;
    }else if (s == "Cloudy"){
        cout << "Rainy" << endl;
    }else if (s == "Rainy"){
        cout << "Sunny" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		String a="0";
		IntStack iStack=new IntStack();
		while(sc.hasNext()){
			String str=sc.next();
			if(str.equals("+")){
				int x=iStack.pop();
				int y=iStack.pop();
				iStack.push(x+y);
				//System.out.println(x+"+"+y);
			}else if(str.equals("-")){
				int x=iStack.pop();
				int y=iStack.pop();
				iStack.push(y-x);				
				//System.out.println(x+"-"+y);
			}else if(str.equals("*")){
				int x=iStack.pop();
				int y=iStack.pop();
				iStack.push(x*y);
				//System.out.println(x+"*"+y);
			}else{
				int m=0;
				int n=1;
				for(int i=str.length()-1;i>=0;i--){
					m+=n*(str.charAt(i)-a.charAt(0));
					n=10*n;
				}
				iStack.push(m);
			}
		}
		System.out.println(iStack.pop());
	}
}

class IntStack{
	private int[] data=new int[256];
	private int sp=0;
	public int pop(){
		sp--;
		return data[sp];
	}
	public void push(int value){
		data[sp]=value;
		sp++;
	}
}

Measured memory_bytes: 26176
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
S = []
walls = 0
for _ in range(H):
    line = INPUT()
    walls += line.count('#')
    S.append(line)

dist = [[INF]*W for _ in range(H)]
dist[0][0] = 1
queue = deque([[0, 0]])
while queue:
    y, x = queue.popleft()
    if y == H - 1 and x == W - 1:
        print(H*W - walls - dist[y][x])
        break

    for dy, dx in [(y, x-1), (y-1, x), (y, x+1), (y+1, x)]:
        if 0 <= dy < H and 0 <= dx < W and S[dy][dx] == '.' and dist[dy][dx] == INF:
            dist[dy][dx] = dist[y][x] + 1
            queue.append([dy, dx])
else:
    print(-1)


Measured memory_bytes: 10112
import math
#sys.exit()
#sorted( ,reverse=True)
R = int(input())
#S,T = map(int, input().split())
#A = list(map(int, input().split()))
#print(N)
#print(S,T)
#print(A)

#print('Yes')
#print('No')

print(2*R*math.pi)

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

int main() {
	// your code goes here
	int x,y,z;
	while( 1 ){
		cin>>x>>y;
		if(x==0 && y==0){break;}
		
		if(x>y){
			z=x;
			x=y;
			y=z;
		
		}
		cout<<x<<" "<<y<<endl;
	}
	
	
	return 0;
}

Measured memory_bytes: 1160
n,k = map(int,input().split())
if n*(n-1)//2 - (n-1) < k:
    print(-1)
else:
    e = n*(n-1)//2 - k
    print(e)
    cnt = 0
    for i in range(1, n):
        for j in range(i+1, n+1):
            print(i,j)
            cnt += 1
            if cnt == e:
                exit()


Measured memory_bytes: 42736
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

int pw2[20];
char s[20];

int main()
{
	pw2[0] = 1;
	for(int i = 1; i<= 10; i++) pw2[i] = pw2[i-1]*2;
	scanf("%s", s);
	int n = strlen(s);
	ll ans = 0;
	for(int i = 0; i< n; i++)
	{
		for(int j = i; j< n; j++)
		{
			ll sum = 0;
			for(int k = i; k<= j; k++)
			{
				sum *= 10;
				sum += s[k]-'0';
			}
			// printf("%lld\n", sum);
			ans += 1LL*sum*pw2[n-1-((j-i)+(i != 0) + (j != n-1))];
		}
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 256
I=lambda:map(int,input().split())
N,M=I()
H=[0]+list(I())
O=[0]+[1]*N
for _ in range(M):
    A,B=I()
    if H[A]<=H[B]:O[A]=0
    if H[A]>=H[B]:O[B]=0
print(O.count(1))

Measured memory_bytes: 20152
#include<bits/stdc++.h>
using namespace std;
int n, k, arr[1000000];
unsigned long long dp[1000000];

long solve(int i) {
	dp[0] = 0;
	dp[1] = abs(arr[0] - arr[1]);

	for (int i = 2; i < n; i++) {
		// dp[i] = min(abs(arr[i]-arr[i-1])+dp[i-1],abs(arr[i]-arr[i-2])+dp[i-2]);
		dp[i] = INT_MAX;
		for (int j = 1; j <= k; j++) {
			if ((i - j) >= 0)
				dp[i] = min(dp[i] , abs(arr[i] - arr[i - j]) + dp[i - j]);
		}

	}

	return dp[n - 1];

}

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

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

	cout <<solve(0);
  
  	

	return 0;
}


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

int main() {
    int N,n = 2;
    cin >>N;
    for(int i=1;i<N+1;i++){
        if(i == n){
            n *=2;
            }
        }
        if(n>1)cout << n/2 <<endl;
        else cout << N <<endl;
    }


Measured memory_bytes: 256
N, M = map(int, input().split())
job_list = {}
for i in range(N):
	day, pay = map(int, input().split())
	if((day-1) in job_list):
		job_list[day-1].append(pay)
	else:
		job_list[day-1] = [pay]

now_date = 0
money = 0
now_job_list = []
sorted = False
for i in range(M):
	if(i in job_list):
		now_job_list.extend(job_list[i])
		sorted = False
	if(len(now_job_list) > 0):
		if(not sorted):
			now_job_list.sort()
			sorted = True
		money += now_job_list.pop()
print(money)


Measured memory_bytes: 61784
#include <iostream>

using namespace std;

int main() {
    int health_a, attack_a, health_b, attack_b;
    cin >> health_a >> attack_a >> health_b >> attack_b;
    while (health_a > 0) {
        health_b -= attack_a;
        if(health_b<=0){
            cout << "Yes" << endl;
            return 0;
        }
        health_a -= attack_b;
    }
    cout << "No" << endl;
    return 0;
}


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

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

    int XX = atoi(s.c_str());

    int a = XX/100, b = XX%100;

    if(a==0 && b==0){
        cout << "NA" << endl;
    } else if(1<=a && a<=12){
        if(1<=b && b<=12) cout << "AMBIGUOUS" << endl;
        else cout << "MMYY" << endl;
    } else {
        if(1<=b && b<=12) cout << "YYMM" << endl;
        else cout << "NA" << endl; 
    }
    
    return 0;
}

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

int main(){
  int A,B;
  cin >> A >> B;
  A %= 3;
  B %= 3;
  if(A+B == 0 || A+B == 3 || A == 0 || B == 0){
    cout << "Possible";
  }
  else{
    cout << "Impossible";
  }
}


Measured memory_bytes: 256
def main():
    N = int(input())
    ai = [int(input()) for i in range(N)]
    
    now = 1
    count = 0
    for i in range(N):
        count = count + 1
        now = ai[now-1]
        if now == 2:
            print(count)
            exit()
    print(-1)
    
    
main()


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

using namespace std;

using ll=long long ;
ll calc(ll x){
    ll res = 0;
    while (x) {
        res += x%10;
        x/=10;
    }
    return res;
}
bool cmp(ll x, ll y) {
    return x*calc(y) <= y*calc(x);
}
void solve() {
    int n; cin >> n;
    ll x=0, y=1;
    for (int _ = 0; _ < n; _++) {
        x += y;
        cout << x << "\n";
        while (cmp(x+10*y, x+y)) {
            y *= 10;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long dp[100010];

int main()
{
	int N,K;
	int h[100015];

cin.tie(0);
ios::sync_with_stdio(false);
	cin>>N>>K;

	for(int i=0;i<N;i++) cin>>h[i];

	for (int i = 0; i < 100010; ++i) dp[i] = LLONG_MAX;	
  
	dp[0]=0;
	dp[1]=abs(h[1]-h[0]);
	for (int i = 2; i < N; ++i) {
		for(int j=1;j<K+1;++j){
                   if(i-j<0)continue;
			dp[i]=min(dp[i],dp[i - j] + abs(h[i] - h[i - j]));
		}
	}
	cout << dp[N-1] << endl;
}


Measured memory_bytes: 4832
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define is(a, b) a == b
#define len(v) ll(v.size())

class UnionFind {
public:
	vector<int> par;//親の番号
    vector<int> rank;//木の深さ
 
	UnionFind(int n){//全ての要素に対して自身が根となるように初期化, 木の深さは0になる
		rep(i,n){
            par.push_back(i);
            rank.push_back(0);
        }
	}
 
	int find(int x) {//木の根を求める
		if(par[x]==x){
            return x;
        }else{
            return par[x]=find(par[x]);
        }
	}
 
	void unite(int x,int y){//xとyの属する集合を併合
        x=find(x);
        y=find(y);
        if(x==y) return;
        if(rank[x]<rank[y]){//木の深さが小さい方を大きい方へ繋げる
            par[x]=y;
        }else{
            par[y]=x;
            if(rank[x]==rank[y]) rank[x]++;
        }
    }

    bool same(int x,int y){//xとyが同じ集合に属するか否か
        return find(x)==find(y);
    }
};
//x以下の要素への最小index, ソートしてから使ってね
template <class T> 
int former(const vector<T> &v, T x){
  return upper_bound(v.begin(), v.end(), x) - v.begin() - 1;
}
//x以上の要素への最小index
template <class T> 
int latter(const vector<T> &v, T x){
  return lower_bound(v.begin(), v.end(), x) - v.begin();
}
//vector書き出し
template <class T>
void cout_vec(const vector<T> &vec1){
  rep(i,len(vec1)){
    cout<<vec1[i]<<' ';
  }
  cout<<'\n';
}
//nCk
template <class T>
T comb(T n,T k){
    T ans=1;
    FOR(i,n-k+1,n+1){
        ans*=i;
    }
    FOR(i,1,k+1){
        ans/=i;
    }
    return ans;
}
//a,bの最大公約数
template <class T>
T gcd(T a,T b) {
	if (b == 0) return a;
	else return gcd(b, a % b);
}
//素因数分解
template <class T>
map<T,T> prime_factor(T x){
    map<T,T> ans;
    for(T i=2;i*i<=x;i++){
        while(x%i==0){
            x/=i;
            ans[i]++;
        }
    }
    if (x!=1){
        ans[x]=1;
    }
    return ans;
}
//約数列挙
template <class T>
vector<T> divisor(T x){
    vector<T> res;
    for(T i=1;i*i<=x;i++){
        if(x%i==0){
            res.push_back(i);
            if(i!=x/i){
                res.push_back(x/i);
            }
        }
    }
    return res;
}
//素数判定
template <class T>
bool is_prime(T x){
    for(T i=2;i*i<=x;i++){
        if(x%i==0){
            return false;
        }
    }
    return x!=1;
}

const ll inf=1e9+7;

ll mult(ll n,ll m){//n^m%infを求める
    if(m==1){
        return n%inf;
    }else if(m%2==0){//オーバーフロー防止のためにn^(m/2)*n^(m/2)を考える
        ll t=mult(n,m/2);
        return (t*t)%inf;
    }else{//奇数の時はn^(m-1)*nを考える
        ll t=mult(n,m-1);
        return (t*n)%inf;
    }
}

typedef pair<ll,ll> P;

ll mod=1e9+7;

ll calc(ll x){
    ll ret=1;
    while(x!=0){
        ret*=(x%mod);
        ret%=mod;
        x--;
    }
    ret=ret%mod;
    return ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,m;
    cin>>n>>m;
    if(n==m+1||m==n+1){
        cout<<(calc(n)*calc(m))%mod<<endl;
    }else if(n==m){
        cout<<(calc(n)*calc(m)*2)%mod<<endl;
    }else{
        cout<<0<<endl;
    }
}

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

namespace cp {
	#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
	#define ROF(i, a, b) for (int i = (b); i >= (a); i--)
	#define REP(a) for (int i = 0; i < (a); i++)
	#define pb push_back
	#define sz(x) (int)(x).size()
 
	typedef long long ll;
	typedef vector<int> vi;
	
	const ll INF = 9223372036854775807;
	const int MOD = 1e9 + 7;
	
	// to_string methods
	string ts(int n) { return to_string(n); }
	string ts(double n) { return to_string(n); }
	string ts(long double n) { return to_string(n); }
	string ts(long long n) { return to_string(n); }
	string ts(char c) { return to_string(c); }
	string ts(bool b) { return b ? "true" : "false"; }
	string ts(string s) { return s; }
	
	template <typename T, typename V>
	string ts(pair<T,V> p) {
		return "{" + ts(p.first) + ", " + ts(p.second) + "}";
	}
	
	template <typename T>
	string ts(T arr[], int len) {
		ostringstream oss;
		oss << "[";
		string delim = "";
		for (int i = 0; i < len; i++) {
		   oss << delim << ts(arr[i]);
		   delim = ", ";
		}
		oss << "]";
		return oss.str();
	}
	
	template<typename Container>
	string ts(const Container &v) {
		ostringstream oss;
		oss << "[";
		string delim = "";
		for (const auto &x : v) {
		   oss << delim << ts(x);
		   delim = ", ";
		}
		oss << "]";
		return oss.str();
	}
	
	template <typename T, typename V>
	string ts(map<T,V> m) {
		ostringstream oss;
		oss << "[";
		string delim = "";
		for (pair<T,V> p : m) {
		   oss << delim;
		   oss << "{" << p.first << ": " << p.second << "}";
		   delim = ", ";
		}
		oss << "]";
		return oss.str();
	}
	
	// https://codeforces.com/blog/entry/62393
	struct custom_hash {
	    static uint64_t splitmix64(uint64_t x) {
	        // http://xorshift.di.unimi.it/splitmix64.c
	        x += 0x9e3779b97f4a7c15;
	        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
	        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
	        return x ^ (x >> 31);
	    }
	    
	    size_t operator()(uint64_t x) const {
        	return splitmix64(x + (chrono::steady_clock::now().time_since_epoch().count()));
    	}
	};
	
	// IO
	void setI(string s) { freopen(s.c_str(), "r", stdin); }
	void setO(string s) { freopen(s.c_str(), "w", stdout); }
	void setIO(string s1, string s2) { setI(s1); setO(s2); }
	void setUsacoIO(string s) { setIO(s + ".in", s + ".out"); }
	
	// Sorting lambda syntax
//	auto check = [&](int x, int y) {
//	    return x < y;
//	};
//
//	set<int, decltype(check)> s(check);
//	map<int, int, decltype(check)> mp(check);
//	priority_queue<int, vi, decltype(check)> pq(check); // remember pq.top() is the largest by default (descending order)
}
using namespace cp;

bool isPalin(const string& s) {
	string t = s;
	reverse(t.begin(), t.end());
	return s.compare(t) == 0;
}

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

	int l, r;
	cin >> l >> r;

	int ret = 0;
	for (int i = l; i <= r; i++) {
		ret += isPalin(ts(i));
	}

	cout << ret << endl;

	return 0;
}

Measured memory_bytes: 3676
#include <bits/stdc++.h>
using namespace std;
int n, w, r, ans, h[200001]; string s, t;

int paint(int i) { return h[i]+(n-i)-(h[n]-h[i]); }

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), 
    cin >> n >> s, r = 0, w = n, t = s; 
    for (int i = 0, j = 1; i < n; i = j++)
            h[j] = h[i] += (s[i] == 'W');
    while (r < w) {
        while (r < n and t[r] == 'R')
            ++r;
        while (w > 0 and t[w-1] == 'W')
            --w;
        if (r < w)
            ++r, --w, ++ans; }
    for (int i = 1; i <= n and ans > 0; ++i)
        ans = min(ans,paint(i));
    cout << ans; }


Measured memory_bytes: 4508
#include <iostream>      // cout, endl, cin
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <cctype>        // isupper, islower, isdigit, toupper, tolower
#include <cmath>

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

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

        cout << N[0] << N.size() - 2 << N[N.size() - 1] << endl;

        return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    char s[51];
    int n,k;

    scanf("%d %d",&n,&k);
    scanf("%s",s);

    switch(s[k-1])
    {
        case 'A':
            s[k-1]='a';break;
        case 'B':
            s[k-1]='b';break; 
        case 'C':
            s[k-1]='c';break;
    }

    printf("%s",s);
    return 0;
}

Measured memory_bytes: 128
import itertools

n = int(input())
a = []
for i in range(n):
    x, y = map(int, input().split())
    a.append((x, y))


ans = 0
lis = [x for x in range(n)]
permutation = itertools.permutations(lis)


def dist(a, b):
    return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5


cnt = 0
for case in permutation:
    cnt += 1
    for i in range(n - 1):
        ans += dist(a[case[i]], a[case[i + 1]])
print(ans / cnt)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
#define all(x) (x).begin(),(x).end()
template <typename T>
std::ostream& operator<<(std::ostream&s,const vector<T>&xs){
    s<<'[';for(size_t i=0;i<xs.size();++i){if(i)s<<' ';s<<xs[i];}return s<<']';
}

vll permpow(const vll& P, ll k) {
    ll n=P.size();
    vll Q(n);
    vll done(n);
    vll cycle;
    for(ll i=0;i<n;++i)if(!done[i]){
        done[i]=true;
        cycle.clear();
        cycle.push_back(i);
        for(ll j=P[i];j!=i;j=P[j]){
            cycle.push_back(j);
            done[j]=true;
        }
        ll m=cycle.size();
        for(ll j=0;j<m;++j)Q[P[cycle[j]]] = cycle[(j+k+1)%m];
    }
    return Q;
}

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

    ll N;cin>>N;
    vll xs(N);for(ll&x:xs)cin>>x;
    ll M,K;cin>>M>>K;
    vll P(N-1);iota(all(P),0);
    for(int i=0,a;i<M&&cin>>a;++i)swap(P[a-2],P[a-1]);
    P=permpow(P,K);
    vll ds(N-1);
    for(ll i=1;i<N;++i)ds[i-1]=xs[i]-xs[i-1];
    cout<<xs[0]<<".0\n";
    for(ll x=xs[0],i=0;i+1<N;++i){
        x+=ds[P[i]];
        cout<<x<<".0\n";
    }
}


Measured memory_bytes: 4600
n="0"+input()
k=int(input())
dp=[[[0]*5,[0]*5] for _ in range(len(n))]
dp[0][1][0]=1
for i in range(1,len(n)):
    x=int(n[i])
    for j in range(4):
        if dp[i-1][1][j]:
            dp[i][1][j+(x!=0)]=1
            if x>1:
                dp[i][0][j+1]+=(x-1)
                dp[i][0][j]+=1
            elif x==1:
                dp[i][0][j]+=1
        if dp[i-1][0][j]:
            dp[i][0][j]+=dp[i-1][0][j]
            dp[i][0][j+1]+=(dp[i-1][0][j]*9)
    dp[i][0][0]=1

print(dp[-1][0][k]+dp[-1][1][k])

Measured memory_bytes: 38384