akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>g[3100];
vector<int>ng[3100];
int deg[3100];
int use[3100];
pair<int,int>edge[31000];
int M;
int N;
int dfs(int a,int b){
	for(int i=a;i<M;i++){
		int L=edge[i].first;
		int R=edge[i].second;
		if(use[L]!=1&&use[R]!=1){
			if(b==0)return -1;
			if(deg[L]<deg[R])swap(L,R);
			int best=-1;
			// use L
			use[L]=1;
			int nb=b-1;
			vector<int>rev;
			for(int j=0;j<g[L].size();j++){
				if(use[g[L][j]]!=1){
					rev.push_back(g[L][j]);
					deg[g[L][j]]--;
				}
			}
			if(!(deg[L]<=1&&deg[R]>1))best=max(best,dfs(i+1,nb));
			for(int j=0;j<rev.size();j++)deg[rev[j]]++;
			// not use L
			use[L]=0;
			rev.clear();
			nb=b;
			for(int j=0;j<g[L].size();j++){
				if(use[g[L][j]]!=1){
					use[g[L][j]]=1;
					nb--;
					rev.push_back(g[L][j]);
				}
			}
			for(int j=0;j<rev.size();j++){
				for(int k=0;k<g[rev[j]].size();k++){
					deg[g[rev[j]][k]]--;
				}
			}
			if(nb>=0&&!(deg[L]>1&&deg[R]<=1))best=max(best,dfs(i+1,nb));
			for(int j=0;j<rev.size();j++){
				for(int k=0;k<g[rev[j]].size();k++){
					deg[g[rev[j]][k]]++;
				}
			}
			use[L]=-1;
			for(int j=0;j<rev.size();j++)use[rev[j]]=-1;
			return best;
		}
	}
	return b;
}
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	N=a;
	//M=b;
	for(int i=0;i<b;i++){
		int p,q;scanf("%d%d",&p,&q);p--;q--;
		g[p].push_back(q);
		g[q].push_back(p);
		deg[p]++;deg[q]++;
		edge[i]=make_pair(p,q);
	}
	for(int i=0;i<a;i++)use[i]=-1;
	for(int i=0;i<a;i++)if(deg[i]<1)use[i]=0;
	int rem=c;
	while(1){
		int at=-1;
		for(int i=0;i<a;i++){
			if(deg[i]>c){
				at=i;break;
			}
		}
		if(~at){
			use[at]=1;
			rem--;
			for(int i=0;i<g[at].size();i++){
				deg[g[at][i]]--;
			}
			deg[at]=0;
		}else break;
	}
	if(rem<0){
		printf("Impossible\n");return 0;
	}
	for(int i=0;i<b;i++){
		if(use[edge[i].first]!=1&&use[edge[i].second]!=1){
			edge[M++]=edge[i];
		}
	}
	if(M>c*c){
		printf("Impossible\n");return 0;
	}
	for(int i=0;i<a;i++)for(int j=0;j<g[i].size();j++){
		if(use[i]!=1&&use[g[i][j]]!=1)ng[i].push_back(g[i][j]);
	}
	for(int i=0;i<a;i++)g[i]=ng[i];
	for(int i=0;i<a;i++)deg[i]=g[i].size();
	int res=dfs(0,rem);
	if(res==-1)printf("Impossible\n");
	else printf("%d\n",c-res);
}

Measured memory_bytes: 1840
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100000

string S;
int N, consL[MAXN + 3], consR[MAXN + 3], ans[MAXN + 3];

int main() {
    cin >> S;
    N = S.length();

    consL[N] = 0;
    for (int i = N - 1; i >= 0; i--) {
        if (S[i] == 'L')
            consL[i] = consL[i + 1] + 1;
        else
            consL[i] = 0;
    }

    consR[0] = 1;
    for (int i = 1; i < N; i++) {
        if (S[i] == 'R')
            consR[i] = consR[i - 1] + 1;
        else
            consR[i] = 0;
    }

    memset(ans, 0, sizeof(ans));
    for (int i = 0; i < N - 1; i++) {
        if (S[i] == 'R' && S[i + 1] == 'L') {
            ans[i] = (consR[i] + 1)/2 + consL[i + 1]/2;
            ans[i + 1] = consR[i]/2 + (consL[i + 1] + 1)/2;
        }
    }

    for (int i = 0; i < N; i++)
        cout << ans[i] << " ";

    cout << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main(){int N, i;
  
			cin >> N ;
           int V[N], C[N];
			for (i=0; i<N; i++){
			cin >> V[i];
				}

			for (i=0; i<N; i++){
				cin>>C[i];
				}
			int ans = 0;
			for (i=0; i<N; i++){
 		 	if(V[i]>C[i]){
	    	ans+=(V[i]-C[i]);
    		}
   			 }
			cout<<ans<<endl;
			return 0;

 }  


Measured memory_bytes: 256
#include <iostream>

int main()
{
    int N;
    std::cin >> N;
    int A[N];
    for(int i=0; i<N; i++){
        std::cin >> A[i];
    }

    unsigned long long kabu = 0;
    unsigned long long money = 1000;
    unsigned long long buy;
    for(int i=0; i<N-1; i++){
        if(A[i+1] > A[i]){
            buy = money / A[i];
            //std::cout << buy << std::endl;
            kabu += buy;
            money -= buy * A[i];
            //std::cout << "money" << money << std::endl;
        }else if(A[i+1] < A[i]){
            money += kabu*A[i];
            kabu = 0;
        }else{//==
            //do nothing
        }
    }
    money += kabu*A[N-1];
    kabu = 0;

    std::cout << money << std::endl;

    //int end;
    //std::cin >> end;
    return 0;
}

Measured memory_bytes: 3588
#0や1のケースに注意
#index out of range

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    a,b,c,k = map(int, input().split())
    if a>=k:
        print(k)
    elif a+b >= k:
        print(a)
    else:
        print(a-(k-(a+b)))

if __name__ == '__main__':
    main()

Measured memory_bytes: 65256
#include<stdio.h>
#include<math.h>

int main(){
	int i,j,n,num[10000],cnt=0;
	int flg;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&num[i]);
	}
	for(i=0;i<n;i++){
		flg=0;
		
		for(j=2;(double)j<=sqrt((double)num[i]);j++){
			if(num[i]%j==0){
				flg=1;
				break;
			}
		}
		if(flg==0){
			cnt++;
		}
	}
	printf("%d\n",cnt);
	return 0;
}

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

#define fr(i,b,e) for(int i=(b); i!=(e); ++i)
#define rep(i,e) for(int i=0; i!=(e); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long int li;
typedef long long int ll;
using graph = vector<vector<int>>;
using edgedp = vector<vector<pair<int,ll>>>;
constexpr int INF=1000000;
//constexpr int MOD=998244353;
constexpr int MOD=1e9+7;
constexpr double PI=3.14159265358979323846;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll a,b;
    cin >> a >> b;
    cout << a*b << "\n";
}   


Measured memory_bytes: 3608
package main
import(
  "fmt"
)
func max(a *int64, b int64)bool{
  if *a<b{
    *a=b
    return true
  }
  return false
}
func main(){
  var n, i, j, k, ans int64
  ans=0
  fmt.Scan(&n)
  var a [][3] int64
  var dp [][3]int64
  a=make([][3]int64, n)
  for i=0;i<n;i++{
    fmt.Scan(&a[i][0], &a[i][1], &a[i][2])
  }
  dp=make([][3]int64, 1000001)
  for i=0;i<n;i++{
    for j=0;j<3;j++{
      for k=0;k<3;k++{
        if j==k{
          continue
        }
        max(&dp[i+1][k], dp[i][j]+a[i][k])
      }
    }
  }
  for j=0;j<3;j++{
    max(&ans, dp[n][j])
  }
  fmt.Println(ans)
}


Measured memory_bytes: 29824
n,ng = map(int,input().split())

MOD    = 10**9+7 
nglist = [0]*(n+1)
dp     = [0]*(n+1)
dp[0]  = 1

for i in range(ng):
  x = int(input())
  nglist[x] = 1
 
for i in range(1,n+1):

  if nglist[i]==1:
    dp[i] = 0
    continue

  if i==1:
    dp[1] = dp[0]
    continue
  
  dp[i] = (dp[i-2] + dp[i-1]) % MOD

print(dp[n])

Measured memory_bytes: 7668
var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));

console.log(main());
function main(){
  var k = o.a() - 1;
  var a = o.l();
  if(a[k--] !== 2)return -1;
  var u = 3, d = 2;
  for(; k >= 0; k--){
    if(a[k] > u)return -1;
    d = a[k] * Math.ceil(d / a[k]);
    u = a[k] * (Math.floor(u / a[k]) + 1) - 1;
    if(d > u)return -1;
  }
  return d + " " + u;
}

Measured memory_bytes: 28248
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
#define INF 1e9
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;
int grid[510][510];
void func(int s,int t){
    if(t-s<3) return ;
    int now=grid[s][s];
    int m=(s+t)/2;
    for (int i = s; i < m; i++)
    {
        for (int j = s; j < m; j++)
        {
            grid[i][j]=now+1;
        }
        
    }
     for (int i = m; i < t; i++)
    {
        for (int j = m; j < t; j++)
        {
            grid[i][j]=now+1;
        }
    }
    func(s,m);
    func(m,t);
}


signed main(){
    int n;
    cin >> n;
    fill(grid[0],grid[n],1);
    func(0,n);
    for (int i = 0; i < n; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            cout<<grid[i][j]<<" ";
        }
        if(i!=n-1)
        cout<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 2432
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define ll long long
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB emplace_back
#define PF emplace_front
#define FILL(a,b) memset(a,b,sizeof(a))
#define lwb lower_bound
#define upb upper_bound
#define lc (x<<1)
#define rc ((x<<1)|1)
using namespace std;
int mini[1100000],tag[1100000],h,w,a[200005],b[200005],maxi=1e9; 
void build(int x,int l,int r){
	if(l==r){
		tag[x]=-l;
		RE;
	}
	int mid=(l+r)>>1;
	tag[x]=-maxi;
	build(lc,l,mid);
	build(rc,mid+1,r);
}
void pd(int x,int l,int r){
	if(l!=r&&tag[x]>-maxi){
		tag[lc]=tag[x];
		tag[rc]=tag[x];
		mini[lc]=tag[x]+l;
		mini[rc]=tag[x]+((l+r)>>1)+1;
	}
	tag[x]=-maxi;
} 
void update(int x,int l,int r,int tl,int tr,int p){
	pd(x,l,r);
	if(l>=tl&&r<=tr){
		tag[x]=p;
		mini[x]=l+tag[x];
		RE;
	}
	if(l>tr||tl>r)RE ;
	int mid=(l+r)>>1;
	update(lc,l,mid,tl,tr,p);
	update(rc,mid+1,r,tl,tr,p);
	mini[x]=min(mini[lc],mini[rc]);
}
int get(int x,int l,int r,int p){
	pd(x,l,r);
	if(l==r)RE mini[x];
	int mid=(l+r)>>1;
	if(mid>=p){
		RE get(lc,l,mid,p);
	}else RE get(rc,mid+1,r,p);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>h>>w;
	FOR(i,1,h)cin>>a[i]>>b[i];
	build(1,1,w);
	FOR(i,1,h){
		if(a[i]==1){
			update(1,1,w,a[i],b[i],maxi);
		}else{
			int t=get(1,1,w,a[i]-1);
			update(1,1,w,a[i],b[i],t+1-a[i]);
		}
		if(mini[1]>=maxi)cout<<"-1\n";
		else cout<<mini[1]+i<<'\n';
	}
	RE 0;
}




Measured memory_bytes: 9252
n,m=map(int,input().split())
X=sorted(map(int,input().split()))
if n>=m:
    r=0
else:
    L=[]
    for i in range(m-1):
        l=X[i+1]-X[i]
        L.append(l)
    L.sort(reverse=True)
    r=X[-1]-X[0]
    for j in range(n-1):
        r-=L[j]
print(r)

Measured memory_bytes: 13960
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long  n, k, ans = 0;
  cin >> n >> k;
  vector<long long> h(n);
  for(int i=0;i<n;i++){
    cin >> h[i];
  }
  sort(h.begin(), h.end());
  for(int i=0;i<n-k;i++){
    ans += h[i];
  }
  
  cout << ans <<endl;
}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
	static boolean check(char[] a, char[]b){
		for(int i=0; i<8; i++){
			if(a[i] != b[i] && a[i] != '*')
				return false;
		}
		return true;
	}



	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		while (true) {
			int n = sc.nextInt();
			int m = sc.nextInt();

			if(n == 0 && m == 0)
				break;

			int money[] = new int[n];
			int hit = 0;
			String[] str1 = new String[n];
			String[] str2 = new String[m];
			char[][] a = new char[n][];
			char[][] b = new char[m][];

			for (int i = 0; i < n; i++) {
				str1[i] = sc.next();
				a[i] = str1[i].toCharArray();
				money[i] = sc.nextInt();

			}
			for (int i = 0; i < m; i++) {
				str2[i] = sc.next();
				b[i] = str2[i].toCharArray();
			}

			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (check(a[i], b[j]))
						hit += money[i];
				}
			}

			System.out.println(hit);

		}
	}

}

Measured memory_bytes: 34692
N = int(input())
A = [int(i) for i in input().split()]

if min(A) >= 0:
    print(N-1)
    for i in range(1, N):
        print(i, i+1)
elif max(A) <= 0:
    print(N-1)
    for i in range(1, N):
        print(N-i+1, N-i)
else:
    if max(A) > - min(A):
        M = 0
        M_index = 0
        for i in range(N):
            if M < A[i]:
                M = A[i]
                M_index = i
        ans = []
        for i in range(N):
            if A[i] < 0:
                ans.append((M_index+1, i+1))
        print(len(ans)+N-1)
        for x, y in ans:
            print(x, y)
        for i in range(1, N):
            print(i, i + 1)

    else:
        M = 0
        M_index = 0
        for i in range(N):
            if M > A[i]:
                M = A[i]
                M_index = i
        ans = []
        for i in range(N):
            if A[i] > 0:
                ans.append((M_index+1, i+1))
        print(len(ans)+N-1)
        for x, y in ans:
            print(x, y)
        for i in range(1, N):
            print(N - i + 1, N - i)


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

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

    //input
    cin >> A >> B;

    ans = (A + B) / 2;

    //output
    if((A + B) % 2 == 0){
        cout << ans << endl;
    }else{
        cout << "IMPOSSIBLE" << endl;
    }

    return 0;
}


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

struct second_order {
    bool operator()(const pair<string,int> &x, const pair<string,int> &y) const {
        return x.second < y.second;
    }
};
int main(void) {
    int64_t N;
    map<string,int> S;
    string s;
    cin >> N;
    for(int i=0;i<N;i++) {
        cin >> s;
        S[s]++;
    }
    priority_queue<pair<string,int>, vector<pair<string,int>>, second_order> que;
    pair<string,int> p;
    for(auto p: S) {
        que.push(p);
    }

    set<string> output;
    pair<string,int> top = que.top();que.pop();
    int64_t before = top.second;
    output.insert(top.first);
    while(!que.empty()){
        top = que.top();
        if(before == top.second) {
            output.insert(top.first);
            que.pop();
        } else {
            break;
        }
    }

    for(auto it:output) {
        cout << it << "\n";
    }

    return 0;
}


Measured memory_bytes: 38380
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using str = string;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vs> vvs;
typedef vector<vc> vvc;
typedef vector<vb> vvb;
using P = pair<ll,ll>;
#define REP(i, n) for (ll i = 0; i < (int)(n); i++)
#define RREP(i, n) for (ll i = (int)(n)-1; i > -1 ; i--)
#define IN(T, x) T x;cin >> x;
#define AIN(T, a, n) vector<T> a(n);REP(i, n){cin >> a[i];}
#define A2IN(T1, a, T2, b, n) vector<T1> a(n);vector<T2> b(n);REP(i, n){cin >> a[i] >> b[i];}
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) SORT(a);reverse(ALL(a))
#define pb push_back
#define mp make_pair
#define PF first
#define PS second
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
template<typename A, size_t N, typename T>void Fill(A (&array)[N], const T &val){fill( (T*)array, (T*)(array+N), val );}
#define OUT(x) cout << x << endl
#define BOUT(b) if(b){OUT("Yes");}else{OUT("No");}
const ll MOD = 100000007;
const ll INF = 10e9;
#define PI 3.14159265369;
ll dx[4] = {1,-1,0,0};
ll dy[4] = {0,0,1,-1};
ll ddx[8] = {1,1,1,-1,-1,-1,0,0};
ll ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main() {
  IN(ll,K);
  IN(ll,N);
  AIN(ll,A,N);
  ll ans = A.at(0) + K - A.at(N-1);
  REP(i,N-1)
    chmax(ans,A.at(i+1) - A.at(i));
  OUT(K - ans);
}



Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  vector<vector<int> > G(n,vector<int>());
  for(int i=0;i<n;i++){
    int u,k;
    cin>>u>>k;
    u--;
    for(int j=0;j<k;j++){
      int c;
      cin>>c;
      c--;
      G[u].push_back(c);
    }
  }
  int d[n];
  memset(d,-1,sizeof(d));
  queue<int> q;
  d[0]=0;
  q.push(0);
  while(!q.empty()){
    int v=q.front();q.pop();
    for(int u:G[v]){
      if(d[u]<0){
	d[u]=d[v]+1;	
	q.push(u);
      }
    }
  }
  for(int i=0;i<n;i++) cout<<i+1<<" "<<d[i]<<endl;;
  return 0;
}

Measured memory_bytes: 3168
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main()
{
	int N, M, K, p, l;
	while (cin >> N, N) {
		vector< vector<int> > mem(N + 1);
		for (int i = 1; i <= N; i++) {
			cin >> M;
			for (int j = 0; j < M; j++) {
				cin >> p;
				mem[i].push_back(p);
			}
		}
		cin >> K;
		vector<int> L(K);
		for (int i = 0; i < K; i++) {
			cin >> l;
			L[i] = l;
		}
		vector<int> res;
		for (int i = 1; i <= N; i++) {
			int j;
			for (j = 0; j < K; j++) {
				if (find(mem[i].begin(), mem[i].end(), L[j]) == mem[i].end())
					break;
			}
			if (j == K) {
				res.push_back(i);
			}
		}
		if (res.size() == 1)
			cout << res[0] << endl;
		else
			cout << -1 << endl;
	}
	return 0;
}

Measured memory_bytes: 3208
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int a[111111];
  int used[111111]={};
  for(int i=0;i<n;i++){
    cin>>a[i];
    a[i]--;
  }
  int ans=0;
  int cnt=0;
  while(1){
    if(cnt==1){
      cout<<ans<<endl;
      return 0;
    }
    if(used[cnt]==1)break;
    used[cnt]=1;
    cnt=a[cnt];
    ans++;
  }
  cout<<-1<<endl;
  return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}


signed main(void) {
    string s;
    cin >> s;
    int n = s.size();
    vector<vi> dp(n+1,vi(4,0));
    string t = "ABC";
    dp[0][0] = 1;
    rep(i,n)rep(j,4){
        //cout << i << " " << j << " " << dp[i][j] << endl;
        if(s[i] == '?'){
            rep(k,3){
                if(j < 3 && t[k] == t[j]){
                    dp[i+1][j+1]  = (dp[i+1][j+1] + dp[i][j]) % MOD;
                }
                dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD;
            }
        }else{
            if(j < 3 && s[i] == t[j]){
                dp[i+1][j+1]  = (dp[i+1][j+1] + dp[i][j]) % MOD;
            }
            dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD;
        }
    }
    cout << dp[n][3] << endl;
}


Measured memory_bytes: 7424
def read_input():
    cards = []
    for i in range(3):
        r = list(map(int, input().split()))
        cards.append(r)

    n = int(input())
    
    blist = []
    for _ in range(n):
        blist.append(int(input()))

    return cards, blist


def get_row(cards, i):
    return cards[i]


def get_col(cards, i):
    col = [cards[j][i] for j in range(3)]
    return col


def get_diag(cards):
    diag = [cards[i][i] for i in range(3)]
    return diag


def get_re_diag(cards):
    diag = [cards[i][2 - i] for i in range(3)]
    return diag


def submit():
    cards, blist = read_input()

    numbers = set(blist)
    bingo = False
    for i in range(3):
        r = get_row(cards, i)
        if set(r) <= numbers:
            print("Yes")
            return

        c = get_col(cards, i)
        if set(c) <= numbers:
            print("Yes")
            return

    if set(get_diag(cards)) <= numbers:
        print("Yes")
        return

    if set(get_re_diag(cards)) <= numbers:
        print("Yes")
        return

    print("No")


if __name__ == "__main__":
    submit()

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
using namespace std;

int main(){
  int N,a;
  cin >> N;
  int i;
  int ans=0;
  for(i=0;i<N;i++){
    cin >> a;
    while(a%2==0){
      ans++;
      a=a/2;
    }
  }
  cout << ans;
}


Measured memory_bytes: 256
from collections import Counter,defaultdict
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
A = defaultdict(int)
for _ in range(N):
    c = Counter(list(input()))
    d = sorted(c.items(),key= lambda x:x[0])
    A[tuple(d)] += 1

SUM = 0
for v in A.values():
    if v > 1:
        SUM += combinations_count(v,2)

print(SUM)

Measured memory_bytes: 74764
// clang-format off
#include <bits/stdc++.h>
using namespace std;
#define ANS(ans) cout<<ans<<endl;
const string YES = "Yes";
const string NO = "No";
// clang-format on

void solve(long long N) {
  if (N / 100 == 7 || (N % 100) / 10 == 7 || (N % 10) == 7) {
    ANS(YES);
  } else {
    ANS(NO);
  }
}

// clang-format off
int main() {
  long long N;
  scanf("%lld",&N);
  solve(N);
  return 0;
}


Measured memory_bytes: 3692
#include<stdio.h>

int main(void){
    char code[4];
    int a = 0;
    for(int i=0; i<4; i++){
        scanf("%c",&code[i]);
    }
    char tmp = code[0];
    for(int i=1; i<4;i++){
        if(tmp == code[i]){
            a = 1;
        }
        tmp = code[i];
    }
    if(a==0){
        printf("Good");
    }else{
        printf("Bad");
    }

    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define rep1(i,n) for(int i=1; i<n; i++)
#define all(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
typedef long long LL;
typedef pair<int, int> P;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> A(n), B(n);
    rep(i, n) cin >> A[i];
    rep(i, n) cin >> B[i];
    if(accumulate(all(A), 0LL) - accumulate(all(B), 0LL)< 0){
        cout << -1 << endl;
        return 0;
    }
    int ans = n;
    vector<LL> p;
    LL q = 0;
    rep(i, n){
        if(A[i] - B[i] > 0) p.pb(A[i] - B[i]);
        else if(A[i] - B[i] < 0) q += B[i] - A[i];
        else ans--;
    }
    sort(all(p));
    reverse(all(p));
    LL sum = 0;
    for(int i=0; sum < q; i++){
        sum += p[i];
        ans++;
    }
    cout << ans-p.size() << endl;
}



Measured memory_bytes: 1788
#include <stdio.h>

#define MAX 100000
int A[MAX];

int partition(int p, int r){

	int x = A[r];
	int i = p - 1;
	int j,tmp;

	for(j=p;j<r;j++){
		if(A[j] <= x){
			i++;
			tmp = A[i];
			A[i] = A[j];
			A[j] = tmp;
		}
	}

	tmp = A[i+1];
	A[i+1] = A[r];
	A[r] = tmp;
	
	return i+1;		

}

int main(void){

	int i,n,r;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&A[i]);
	}
	
	r = partition(0, n-1);
	
	for(i=0;i<n;i++){
		if(i != 0){ printf(" "); }
		if(i == r) printf("[");
		printf("%d",A[i]);
		if(i == r) printf("]");
	}

	printf("\n");
	

return 0;

}



Measured memory_bytes: 2236
/*
sonu_verma1
*/
#include <bits/stdc++.h>
// For policy based data structure
/*#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> */
using namespace std;
/*using namespace __gnu_pbds; 
typedef tree<int, null_type, less<int>, rb_tree_tag, 
             tree_order_statistics_node_update> 
    new_data_set;*/
 
#define MD 1000000007
#define X first
#define Y second
#define pb push_back
#define debug(val, ch) cout <<val <<ch
#define FOR(i, st, en, ch) for(register int i = (st); i <= (en) ; i += (ch))
#define RFOR(i, st, en, ch) for(register int i = (st); i >= (en) ; i -= (ch))
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
 
typedef long long int ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<int, bool> pib;
typedef pair<bool, int> pbi;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
/*********************************************************************/
void test(int r)
{
    int n;
    cin>>n;
    vector<int>a(n),b(n),c(n);
    int i,j;
    for(i=0;i<n;i++)
        cin>>a[i]>>b[i]>>c[i];
    vector<vector<int>>dp(n,vector<int>(3,0));
    dp[0][0]=a[0];
    dp[0][1]=b[0];
    dp[0][2]=c[0];
    for(i=1;i<n;i++)
    {
        dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
        dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
        dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];
    }
    cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
}
/***********************************************************************/
int main()
{
    fast();
    int t=1,r;
    // cin>>t;
    for(r=1;r<=t;r++)
        test(r);
    return 0;
}

Measured memory_bytes: 9808
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define repp(i, m, n) for(int i = m, i##_len = (n); i < i##_len; ++i)
#define reprev(i, n) for(int i = (n-1LL); i >= 0; --i)
#define all(x) (x).begin(), (x).end()
template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s, t, u;
    int a, b;
    cin >> s >> t >> a >> b >> u;
    if (s == u) cout << a - 1 << " " << b << "\n";
    if (t == u) cout << a << " " << b - 1 << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>

using namespace std;

#define int long long

const int MOD = 1e9 + 7;

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;
	vector<int> a(n);
	for (auto &t : a) {
		cin >> t;
	}
	int ans = 0;
	for (int i = 0; i < 61; i++) {
		vector<int> cnt(2);
		for (int j = n - 1; j >= 0; j--) {
			int b = ((a[j] >> i) & 1);
			int c = (1LL << i) % MOD;
			c *= cnt[b ^ 1];
			c %= MOD;
			ans += c;
			ans %= MOD;
			cnt[b]++;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 2560
#include <stdio.h>

int main(void)
{
	int a;
	int b;
	int c;
	int d;
	int e;
	int f;
	double x;
	double y;
	int D;
	
	while (scanf("%d %d %d %d %d %d", &a, &b, &c, &d, &e, &f) != EOF){
		D = a * e - b * d;
		b *= -1;
		d *= -1;
		x = (e * c + b * f) / (D * 1.0);
		y = (d * c + a * f) / (D * 1.0);
		if (x == 0){
			x = 0;
		}
		if (y == 0){
			y = 0;
		}
		
		printf("%.3lf %.3lf\n", x, y);
	}
	
	return (0);
}

Measured memory_bytes: 636
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<map>
#include<string>
#include<sstream>
using namespace std;
int inf = 1000000000;

int main(){

  string s, t;
  cin >> s >> t;
  if( s[0] == t[2] && s[1] == t[1] && s[2] == t[0] ) cout << "YES" << endl;
  else cout << "NO" << endl;


  return 0;
}





//


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>

struct node{
int key;
struct node *prev, *next;
};

struct node *nil;

void insert(int);
void delete(struct node*);
struct node* search(int);
void listPrint(void);

int main(){
  int n,i,x;
  char str[15];

  scanf("%d",&n);
  nil = (struct node*)malloc(sizeof(struct node));
  nil->next = nil;
  nil->prev = nil;

  for(i = 0; i<n;i++){
    scanf("%s",str);
    if(str[0]== 'i'){
      scanf("%d",&x);
      insert(x);
    }else if(str[0]=='d'){
      if(str[6]=='\0'){
        scanf("%d",&x);
        delete(search(x));
      }else if(str[6]=='F'){
        delete(nil->next);
      }else{
        delete(nil->prev);
      }
    }
  }
  listPrint();
  return 0;
}




void insert(int key){
  struct node* newnode = (struct node*)malloc(sizeof(struct node));
  newnode->key = key;
  newnode->next = nil->next;
  nil->next->prev = newnode;
  nil->next = newnode;
  newnode->prev = nil;
 }

void delete(struct node* delnode){
  if(delnode == nil){;
  }else{
    delnode->prev->next = delnode->next;
    delnode->next->prev = delnode->prev;
    free(delnode);
  }
}

struct node* search(int key){
  struct node* searchnode = nil->next;
  while(searchnode != nil && searchnode->key != key){
    searchnode = searchnode->next;
  }
return searchnode;
}


void listPrint(){
  int i = 0;
  struct node* n= nil->next;
  while(1){
    if(n==nil)break;
    if(i>0)printf(" ");
    i++;
    printf("%d",n->key);
    n=n->next;
  }
  printf("\n");
}

Measured memory_bytes: 32968
#include <iostream>
#include <string>
using namespace std;
int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };
string field[8];

void bomb(int x, int y) {
	field[y][x] = '0';
	for (int i = 0; i < 4; ++i) {
		int nx = x + dx[i]; int ny = y + dy[i];
		for (int j = 0; j < 3; ++j) {
			if (0 <= nx && nx < 8 && 0 <= ny && ny < 8 && field[ny][nx] == '1') bomb(nx, ny);
			nx += dx[i]; ny += dy[i];
		}
	}
	return;
}

int main() {
	int n, sx, sy;

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 8; ++j) {
				cin >> field[j];
		}
		cin >> sx >> sy;
		sx--; sy--;

		bomb(sx, sy);

		cout << "Data " << i << ":" << endl;
		for (int i = 0; i < 8; ++i) {
			cout << field[i] << endl;
		}
		
	}
	return 0;
}

Measured memory_bytes: 1204
import java.util.*;
class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s[]=in.nextLine().split("");
        long no=0,sum = 0;
        for (String var:s){
            sum += Long.parseLong(var);
            no = no*10+Long.parseLong(var);
        }
        if (no%sum==0) System.out.println("Yes");
        else System.out.println("No");
    }
}

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

int main() {
  string s,t;
  cin >> s >> t;
  cout << t+s << endl;
  return 0;
}


Measured memory_bytes: 256
import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;
import std.array;
import std.math;

void stringsTo(string, T...)(string str, ref T t) {
  auto s = str.split();
  assert(s.length == t.length);
  foreach(ref ti; t) {
    ti = s[0].to!(typeof(ti));
    s = s[1..$];
  }
}

long INF = pow(10, 9);

struct Node {
  int   u; // :u ノードのインデックス
  ulong k; // :k u の出次数
  int[] v; // :v u に隣接する頂点の番号
  int[int] w; // :w 隣接する頂点への重み
};

class Graph {
  public int n;
  public Node[] nodes;
  public long[][] dist;

  this(int n) {
    this.n = n;
    this.nodes = new Node[n];
    foreach (int i, ref node; this.nodes) {
      node.u = i;
    }
    this.dist = new long [][](n,n);
  }

  void addGraphEdge(int u, int v, int w) {
    this.nodes[u].v ~= v;
    this.nodes[u].w[v] = w;
    this.nodes[u].k = this.nodes[u].v.length;
  }

  void warshallFloyd() {
    for (int i = 0; i < this.nodes.length; i++ ) {
      for (int j = 0; j < this.nodes.length; j++ ) {
	int* val = j in this.nodes[i].w;
	if (val != null) {
	  this.dist[i][j] = *val;
	} else {
	  this.dist[i][j] = INF;
	}
      }
      this.dist[i][i] = 0;
    }

    for (int k = 0; k < this.nodes.length; k++) {
      for (int i = 0; i < this.nodes.length; i++) {
	for (int j = 0; j < this.nodes.length; j++) {
	  if (this.dist[i][k] != INF && this.dist[k][j] != INF) {
	    this.dist[i][j] = min(this.dist[i][j], this.dist[i][k] + this.dist[k][j]);
	  }
	}
      }
    }
  }
}

void main()
{

  string lines;
  string buf;

  while (!stdin.eof) {
    buf = stdin.readln();
    lines ~= buf;
  }

  string[] array = splitLines(lines);
  //writeln(to!string(array));
  int N,M,R;
  stringsTo(array[0], N, M, R);
  Graph graph = new Graph(N);
  int[] rarr = array[1].split(" ").map!( (s) => s.to!int ).array;
  sort(rarr);

  foreach (str; array[2..M+2]) {
    int s,t,d;
    stringsTo(str,s,t,d);
    s = s - 1;
    t = t - 1;
    graph.addGraphEdge(s,t,d);
    graph.addGraphEdge(t,s,d);
  }

  graph.warshallFloyd();
  long ans = INF;

  // Rから2つ選ぶ全探索
  //writeln(join(rarr.map!(s => s.to!string), ","));

  import std.algorithm : nextPermutation;

  do
    {
      long s = 0;
      for (int i = 1; i < rarr.length; i++) {
        //writeln(rarr[i-1]-1, ",", rarr[i]-1);
        s += graph.dist[rarr[i-1] - 1][rarr[i] - 1];
      }
      //writeln(s);
      ans = min(s, ans);
    }
  while(nextPermutation(rarr));

  writeln(ans);

  //writeln(graph.dist);
  //cat in2.txt | ./D.d
  //[[0, 2, 4],
  // [2, 0, 2],
  // [4, 2, 0]]
}

Measured memory_bytes: 8572
#include <bits/stdc++.h>
using namespace std;
int main(void){
   int N;
   cin >> N;
   vector<int> X(N);
   for(int i = 0; i < N; i++) cin >> X[i];
   sort(X.begin(),X.end());
   int H,HMin;
   HMin = 1000000;
   for(int i = 1; i <= 100; i++){
       H = 0;
       for(int j = 0; j < N; j++) H += (X[j]-i)*(X[j]-i);
       HMin = min(HMin,H);
   }
   cout << HMin << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,x,n) for(int i=x;i<(int)n;i++)
#define rep(i,n) REP(i,0,n)
#define sp(p) cout<<setprecision(16)<<fixed<<p<<endl;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define SORT(a) sort(all(a))
#define RSORT(a) sort(rall(a))
#define UNIQ(a) unique(all(a))
#define UNIQNUM(a) UNIQ(a)-a.begin()
#define UNIQIT(a) a.erase(UNIQ(a), a.end());
#define VOUT(v,i) rep(i,v.size())cout<<v[i]<<(i==v.size()-1?"\n":" ");
#define vout(v) VOUT(v,z);
#define vdbg(v,i) cout<<#v<<": ";for(int i=0;i<(int)v.size();i++){cout<<v[i]<<" ";}cout<<"\n";
#define vmin(v) *min_element(all(v))
#define vmax(v) *max_element(all(v))
#define vsum(v) accumulate(all(v), 0LL)
#define MOUT(m,r,c) rep(i,r){rep(j,c){cout<<m[i][j]<<" ";}cout<<endl;}
#define mout(m) MOUT(m,m.size(),m[0].size())
#define debg(a) cout<<#a<<": "<<a<<endl;
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
#define digit(a) to_string(a).length();
template<class T>inline int out(const T &t){ print(t); putchar('\n'); return 0; }
template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef vector<ll> V;
typedef vector<vector<ll>> VV;
// const long long MOD=1000000007;
const long long INF = 1e18;
#define EPS (1e-7)
#define PI (acos(-1))
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) { a = b; return true; }
    return false;
}
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) { a = b; return true; }
    return false;
}


void solve(long long A, long long B){
    for (long long i = 1; i <= 1000; i++) {
        ll ten8 = floor(i*0.08);
        ll ten10 = floor(i*0.1);
        if(ten8==A && ten10==B){
            cout << i << endl;
            return;
        }
    }
    cout << -1 << endl;
    return;
}

int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(A, B);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
using VI = vector<long>;


int main() {
    VI v(3);
    long k;
    for (int i = 0; i < 3; i++) {
        cin >> v[i];
    }
    cin >> k;
    sort(v.begin(), v.end());
    cout << long(pow(2, k) * v.back()) + v[0] + v[1] << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
constexpr long long MOD = 1000000007;
using ll = long long;
int main() {
    ll a, b, c, k;
    cin >> a >> b >> c >> k;
    ll ans = 0;
    ans += min(a, k);
    k -= a;
    if(k<=0){
        cout << ans << endl;
        return 0;
    }
    k -= b;
    if(k<=0){
        cout << ans << endl;
        return 0;
    }
    ans -= min(k, c);
    cout << ans << endl;
}


Measured memory_bytes: 3632
#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")

// Begin {{{
using namespace std;

#ifndef DEBUG
#define dump(...)
#endif

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T>
inline vector<T> make_v(const T &initvalue, intmax_t sz) {
    return vector<T>(sz, initvalue);
}

template <class T, class... Args>
inline auto make_v(const T &initvalue, intmax_t sz, Args... args) {
    return vector<decltype(make_v<T>(initvalue, args...))>(sz, make_v<T>(initvalue, args...));
}

constexpr int INF = 0x3f3f3f3f;
constexpr int64_t LINF = 0x3f3f3f3f3f3f3f3fLL;
// }}} End

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    size_t N, K; cin >> N >> K;

    vector<int> h(N);
    for (auto &hi: h) cin >> hi;

    vector<int> dp(N, INF);
    dp[0] = 0;
    for (size_t i = 0; i < N; ++i) {
        for (size_t j = 1; j <= K; ++j) {
            if (i + j < N) {
                chmin(dp[i + j], abs(h[i + j] - h[i]) + dp[i]);
            }
        }
    }

    cout << dp[N - 1] << "\n";

    return 0;
}


Measured memory_bytes: 1024
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] r = new int[n];
		
		for (int i = 0; i < n; i++) {
			r[i] = sc.nextInt();
		}
		
		int maxv = r[1] - r[0];
		int minv = r[0];
		
		for (int j = 1; j < n; j++) {
			maxv = Math.max(maxv, r[j] - minv);
			minv = Math.min(minv, r[j]);
		}
		
		System.out.println(maxv);
	}
}

Measured memory_bytes: 100112
using System;

namespace atcoderA
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string N = Console.ReadLine();
            if (N[0] == N[1] && N[0] == N[2])
            {
                Console.WriteLine("Yes");
            }
            else if (N[1] == N[2] && N[2] == N[3])
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }
    }
}

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

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using mii = map<int, int>;
using msi = map<string, int>;
using pii = pair<int, int>;

struct Edge {
    int to;     // 辺の行き先
    int weight; // 辺の重み
    Edge(int t, int w) : to(t), weight(w) { }
};
using Graph = vector<vector<Edge>>;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b,k;
    cin >> a >> b >> k;
    if(a >= k) a -= k;
    else {
        k -= a;
        a = 0;
        b -= k;
        if(b < 0) b = 0;
    }
    cout << a << " " << b;
    return 0;
}

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

int main(int argc, char** argv) {
   int a, b, c;
   cin >> a >> b >> c;

   int count = 0;
   if (a == 5) {
      count++;
   }

   if (b == 5) {
      count++;
   }

   if (c == 5) {
      count++;
   }

   if (count >= 2) {
      cout << "YES" << endl;
   }
   else {
      cout << "NO" << endl;
   }

   return 0;
}


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

#define LL long long
#define RG register

using namespace std;
template<class T> inline void read(T &x) {
	x = 0; RG char c = getchar(); bool f = 0;
	while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;
	while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();
	x = f ? -x : x;
	return ;
}
template<class T> inline void write(T x) {
	if (!x) {putchar(48);return ;}
	if (x < 0) x = -x, putchar('-');
	int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;
	for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;
}
const int N = 2e5 + 10, inf = 1e9;
struct node {
	int c, w, u;
	bool operator < (const node &z) const {
		return w > z.w;
	}
};
priority_queue<node> q;
vector<int> e[N];
map<int, vector<int> > E[N];
int n, m;
map<int, int> f[N];
void dijkstra() {
	while (!q.empty()) {
		node u = q.top(); q.pop();
		if (f[u.u][u.c] != u.w) continue;
		if (f[u.u][0] > u.w)
			f[u.u][0] = u.w,  q.push((node) {0, u.w, u.u});
		if (!u.c) {
			for (auto v : e[u.u])
				if (f[u.u][v] > u.w + 1)
					f[u.u][v] = u.w + 1, q.push((node) {v, u.w + 1, u.u});
		}
		else {
			for (auto v : E[u.u][u.c])
				if (f[v][u.c] > u.w) f[v][u.c] = u.w, q.push((node) {u.c, u.w, v});
		}
	}
	return ;
}
int main() {
	read(n), read(m);
	for (int i = 1, p, q, c; i <= m; i++) {
		read(p), read(q), read(c);
		e[p].push_back(c); e[q].push_back(c);
		E[p][c].push_back(q); E[q][c].push_back(p);
		f[p][c] = f[q][c] = inf;	
	}
	for (int i = 2; i <= n; i++) f[i][0] = inf;
	f[1][0] = 0;
	q.push((node) {0, 0, 1});
	dijkstra();
	int ans = inf;
	for (auto i : f[n]) ans = min(ans, i.second);
	printf("%d\n", ans > n ? -1 : ans);
	return 0;
}


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

#define ALL(v) (v).begin(), (v).end()
#define rep(i, n) for (ll i = 0, __##i##_length = (n); i < __##i##_length; i++)
#define rep_reverse(i, n) for (ll i = (n)-1; 0 <= i; i--)
#define FOR(i, from, to)                                                       \
  for (ll i = (from), __##i##_end = (to); i < __##i##_end; i++)
#define FOR_REVERSE(i, from, to)                                               \
  for (ll i = (to)-1, __##i##_end = (from); __##i##_end <= i; i--)
#define foreach(e, v) for (const auto e : (v))
#define vfree(v) std::vector<int>().swap(v)
#define DEBUG(x) cout << #x << " = " << (x) << endl

using namespace std;
typedef int64_t ll;
typedef vector<ll> llv;
typedef vector<llv> llvv;

#define MOD (ll)1000000007

int main() {
  string s;
  cin >> s;
  ll q;
  cin >> q;
  bool is_reverse = false;
  rep(_, q) {
    ll t;
    cin >> t;
    if (t == 1) {
      is_reverse = !is_reverse;
    } else {
      ll f;
      cin >> f;
      char c;
      cin >> c;
      if (f == 1) {
        if (is_reverse)
          s.insert(s.end(), c);
        else
          s.insert(s.begin(), c);
      } else {
        if (is_reverse)
          s.insert(s.begin(), c);
        else
          s.insert(s.end(), c);
      }
    }
  }
  if (is_reverse)
    reverse(ALL(s));
  cout << s << endl;
}

Measured memory_bytes: 900
#!/usr/bin/python
# -*- Coding: utf-8 -*-

azi = []
N,L = map(int,input().split())

for i in range(N):
    azi.append(L+i)
all = sum(azi)

wa = 0
ans=0
min = 999999

for i in range(N):
    wa = 0
    for j in range(N):
        if (i != j):
            wa += azi[j]
    if abs(all-wa) < min:
        min = abs(all-wa)
        ans = wa 

print (ans)

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

int main() {
    string s;
    cin>>s;
    int loop=0;
    for(int i=0;i<s.size();i++){
        if(s.at(i)=='A'){
            for(int k=s.size()-1;k>i;k--){
                if(s.at(k)!='Z') continue;
                else if(s.at(k)=='Z'){
                    cout<<k-i+1<<endl;

                    loop=1;
                    break;
                }
            }
            if(loop==1) break;
        }else{
            continue;
        }

    }
}


Measured memory_bytes: 640
x,y,z,k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse = True)
b.sort(reverse = True)
c.sort(reverse = True)
li = []
box = []
for i in a:
    for j in b:
        li.append(i + j) 
li.sort(reverse = True)
li = li[:min(k,x*y)]
for i in c:
    for j in li:
        box.append(i + j)
box.sort(reverse = True)
for i in range(k):
    print(box[i])

Measured memory_bytes: 162528
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod = 1e9+7;
int main() {
  ll X,Y;
  cin >> X >> Y;
  ll A = min(X,Y);
  ll B = max(X,Y);
  if(A == B) puts("Brown");
  else if(B-A == 1) puts("Brown");
  else puts("Alice");
  return 0;
}


Measured memory_bytes: 256
mod = 10 ** 9 + 7
N = int(input())
A = [int(a) for a in input().split()]
A.sort()

if N % 2 != 0:
    if A[0] == 0:
        for i in range(2, N, 2):
            if not (A[i] == i and A[i-1] == i):
                print(0)
                exit()
        order_count = 2 ** ((N - 1) // 2) % mod
    else:
        print(0)
        exit()

else:
    for i in range(1, N, 2):
        if not (A[i] == i and A[i-1] == i):
            print(0)
            exit()
    order_count = 2 ** (N // 2) % mod 

print(order_count)

Measured memory_bytes: 13880
import sys
input = sys.stdin.readline
from collections import deque


n, m = map(int, input().split())

GRAPH = {i:[] for i in range(1, n + 1)}
for _ in range(m):
    a, b = map(int, input().split())
    GRAPH[a].append(b)
    GRAPH[b].append(a)

DISTANCE = {i:-1 for i in range(1, n + 1)}
DISTANCE[1] = 0
QUEUE = deque([1])
while QUEUE:
    now = QUEUE.popleft()
    for v in GRAPH[now]:
        if DISTANCE[v] != -1:
            continue
        DISTANCE[v] = DISTANCE[now] + 1
        QUEUE.append(v)

print("POSSIBLE" if DISTANCE[n] == 2 else "IMPOSSIBLE")


Measured memory_bytes: 108512
N,W=map(int,input().split())
I=[[*map(int,input().split())]for _ in[0]*N]
C=[0]*-~W
for i in range(1,N+1):
 v,w=I[~-i]
 for j in range(W,w-1,-1):
  t=v+C[j-w]
  if t>C[j]:C[j]=t
print(C[W])


Measured memory_bytes: 5924