akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1000000010
#define EPS 1e-9
#define fst first
#define scd second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  int a[100000];
  int cnt[100000]={0};
  vector<int> in(100000);
  rep(i,n){
    cin>>a[i];
    a[i]=(i+a[i])%n;
    in[a[i]]++;
  }
  //rep(i,n) cout<<a[i]<<" ";
  //cout<<endl;
  int ans=n;
  queue<int> p;
  rep(i,n){
    if(in[i] == 0){
      p.push(i);
    }
  }
  while(!p.empty() ){
    int num=p.front();
    p.pop();
    ans--;
    num=a[num];
    in[num]--;
    if(in[num] == 0) p.push(num);
  }
      
      
  cout<<ans<<endl;

  return 0;
}



Measured memory_bytes: 4776
#!/usr/bin/env python3
import sys, os
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
if os.environ.get("USER") == "shun":
    def debug(*args): print(*args, file=sys.stderr)
else:
    print("NO DEBUG", file=sys.stderr)
    def debug(*args): pass
def exit(): sys.exit(0)


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


if n % 2 == 0:
    m = n // 2
else:
    m = n // 2 + 1

if k <= m:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 38384
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define reps(i,s,n) for(int (i) = (s); (i) < (n); ++(i))
#define rep(i,n) reps(i,0,n)
using ll = long long;
     
int main(){
	int n;
	cin >> n;
	vector<int> a(n,0);
	rep(i,n) cin >> a[i];
	int ans = 0;
	int light = 1;


	rep(i,n){
		light = a[light-1];
		//cout << light << endl;
		if(light == 2){
			ans = i;
			break;		
		}
	}	
	if(light == 2) cout << ans+1 << endl;
	else cout << -1 << endl;


	return 0;
}

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

#define ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double

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

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

#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N = 100005;
char s[N];
int d[N];
struct dsu{
    int n;
    vector<int> par, sm;
    dsu(int n) : n(n), par(n), sm(n){
        iota(par.begin(), par.end(), 0);
		for(int i = 1; i < n; i++) sm[i] = (d[i] - d[i - 1] + 26) % 26;
    }
    int root(int x){
        return x == par[x] ? x : (par[x] = root(par[x]));
    }
    bool merge(int x, int y){
        x = root(x); y = root(y);
        if(x == y) return 0;
        par[x] = y;
		sm[y] += sm[x];
		sm[y] %= 26;
        return 1;
    }
};

int main(){
	scanf("%s", s + 1);
	int q; sd(q);
	int n= strlen(s + 1);
	int mid = n / 2;
	for(int i = 1; i <= mid; i++) d[i] = (s[i] - s[n + 1 - i] + 26) % 26;
	vector<vector<int>> events(n + 1);
	dsu D(mid + 2);
	for(int i = 1; i <= q; i++){
		int l, r; sd(l); sd(r);
		if(n % 2 == 1 && l == mid + 1 && r == mid + 1) continue;
		if(n % 2 == 1 && l == mid + 1 &&r != mid + 1){
			D.merge(n + 1 - r, mid + 1);
			continue;
		}
		if(n % 2 == 1 && r == mid + 1 && l != mid + 1){
			D.merge(l, mid + 1);
			continue;
		}
		int a = l > mid, b = r > mid;
		int vl = a ? n + 1 - l : l;
		int vr = b ? n + 1 - r : r;

		if(!a && !b){
			D.merge(vl, vr + 1);
		}

		if(!a && b){
			// [vl ... mid] U [vr ... mid]
			if(vl > vr) swap(vl, vr);
			D.merge(vl, vr);
		}
		if(a){
			D.merge(vr, vl + 1);
		}
	}
	for(int i = 1; i <= mid + 1; i++) if(D.root(i) == i){
		if(D.sm[i] != 0){
			printf("NO\n");
			return 0;
		}
	}
	printf("YES\n");
}

Measured memory_bytes: 3328
//Δ_F
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 111111;
const int inf = 1e9;
int ab(int x,int y){
	if(x>y)
		return x-y;
	return y-x;
}
int n,m,q,w,a[N][2],b[N][2][2][2];
char s[N];
struct node{
	int e[2],s;
	node(int x=0,int y=0,int z=0){
		e[0]=x,e[1]=y,s=z;
	}
};
vector<node> v1,v2;
void dfs(int k,node p,int las,int rev,vector<node>&v){
	v.push_back(p);
	if(k>=2)
		return;
	int i,x;
	node q;
	for(i=0;i<2;i=i+1){
		if(las==i)
			continue;
		x=p.e[i];
		x=b[x][i][a[p.e[i^1]][i^1]^rev][a[x][i]^1];
		if(!x)
			continue;
		q=p;
		q.e[i]=x;
		q.s+=ab(x,p.e[i]);
		dfs(k+1,q,i,rev,v);
	}
}
bool ok(int i,int u,int s,int t){
	return (s==t)||((s>t)^a[u][i]);
}
void chk(node p,node q){
	int i,o=p.s+q.s+ab(p.e[0],q.e[0])+ab(p.e[1],q.e[1]);
	for(i=0;i<2;i=i+1)
		if(ok(i,p.e[i],p.e[i^1],q.e[i^1])&&ok(i^1,q.e[i^1],p.e[i],q.e[i]))
			w=min(w,o);
}
int main()
{
	int i,j,x,y;
	scanf("%d%d%d",&n,&m,&q);
	scanf("%s",s+1);
	for(i=1;i<=n;i=i+1)
		a[i][0]=s[i]=='E';
	for(i=1;i<=n;i=i+1){
		for(j=0;j<2;j=j+1)
			b[i][0][0][j]=b[i-1][0][0][j];
		b[i][0][0][a[i][0]]=i;
	}
	for(i=n;i;i=i-1){
		for(j=0;j<2;j=j+1)
			b[i][0][1][j]=b[i+1][0][1][j];
		b[i][0][1][a[i][0]]=i;
	}
	scanf("%s",s+1);
	for(i=1;i<=m;i=i+1)
		a[i][1]=s[i]=='S';
	for(i=1;i<=m;i=i+1){
		for(j=0;j<2;j=j+1)
			b[i][1][0][j]=b[i-1][1][0][j];
		b[i][1][0][a[i][1]]=i;
	}
	for(i=m;i;i=i-1){
		for(j=0;j<2;j=j+1)
			b[i][1][1][j]=b[i+1][1][1][j];
		b[i][1][1][a[i][1]]=i;
	}
	while(q--){
		scanf("%d%d%d%d",&i,&j,&x,&y);
		v1.clear(),v2.clear();
		dfs(0,node(i,j),-1,0,v1);
		dfs(0,node(x,y),-1,1,v2);
		w=inf;
		for(i=0;i<v1.size();i=i+1)
			for(j=0;j<v2.size();j=j+1)
				chk(v1[i],v2[j]);
		if(w>=inf)
			w=-1;
		printf("%d\n",w);
	}
	return 0;
}

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

int main() {
  int a, b;
  cin >> a >> b;
  for (int n = 0; n < 10000; ++n) {
    int za = n*8/100;
    int zb = n*10/100;
    if (a == za && b == zb) {
      cout << n << endl;
      return 0;
    }
  }
  cout << -1 << endl;
  return 0;
}

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

int main(){
  int a, b;
  cin >> a >> b;

  if ( a < b ) {
    cout << "a < b" << endl;
  } else if ( a > b ) {
    cout << "a > b" << endl;
  } else if ( a == b ) {
    cout << "a == b" << endl;
  }

  return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
 
#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()
 
using namespace std;
using ll  = long long;
using pll = pair<ll, ll>;
 
const ll MOD  = 1e9+7;
const ll LINF = 1LL << 60;
const int INF = 1e9 + 7;

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

    bool notRV = true;

    rep(i, q){
        ll t;
        cin >> t;
        if(t == 1)notRV = !notRV;
        else{
            ll f;
            char c;
            cin >> f >> c;
            if(f == 1){
                if(notRV)s.insert(s.begin(), c);
                else s.push_back(c);
            }
            else {
                if(notRV)s.push_back(c);
                else s.insert(s.begin(), c);
            }
            
        }
    }

    if(!notRV)reverse(ALL(s));
    cout << s << endl;
}

Measured memory_bytes: 900
import sys
readline = sys.stdin.readline


sys.setrecursionlimit(10**7)
class LowLinks:
    def __init__(self, edges, edges_num:int):
        """edges[u]: all vertexes connected with vertex 'u'
        edges_num: number of edges of graph
        the root of DFS-tree is vertex 0
        """
        self.edges = edges
        self.V = len(edges)
        self.order = [-1]*V
        self.low = [float('inf')]*V
        self.bridges = []
        # if degreee(root) > 1 and graph is tree: root is articulation
        self.articulations = []
        if len(edges[0]) > 1 and edges_num == self.V-1:
            self.articulations.append(0)
        self.k = 0

    def build(self):
        self.dfs(0, 0)

    def get_bridges(self)->tuple:
        return self.bridges

    def get_articulations(self)->tuple:
        return self.articulations

    def dfs(self, v:int, prev:int):
        self.order[v] = self.k
        self.k += 1
        self.low[v] = self.order[v]
        is_articulation = False
        for to in self.edges[v]:
            if self.order[to] < 0: # not visited
                self.dfs(to, v)
                self.low[v] = min(self.low[v], self.low[to])
                if self.low[v] < self.low[to]:
                    self.bridges.append((v, to))
                is_articulation |= self.order[v] <= self.low[to]
            elif to != prev:
                self.low[v] = min(self.low[v], self.order[to])
        if v>0 and is_articulation:
            self.articulations.append(v)

if __name__ == "__main__":
    V,E = map(int, readline().split())
    edges = [[] for _ in range(V)]
    for _ in range(E):
        s,t = map(int, readline().split())
        edges[s].append(t)
        edges[t].append(s)
    lowlinks = LowLinks(edges, E)
    lowlinks.build()
    articulations = lowlinks.get_articulations()
    if articulations:
        print(*sorted(articulations), sep="\n")



Measured memory_bytes: 19364
#include<bits/stdc++.h>
using namespace std;
/**
********************************************************************
******************* Author:Bisnu sarkar ****************************
********************************************************************
**/
#define ull            unsigned long long
#define ll             long long
#define vi             vector<int>
#define pb             push_back
#define mp             make_pair
#define pii            pair<int,int>
#define vit            vector<int> :: iterator
#define sit            set<int> :: iterator
#define vrit           vector<int> :: reverse iterator
#define ff             first
#define ss             second
#define endl           '\n';
#define what_is(x)     cerr << #x << " is " << x << endl;
///*....Debugger....*/
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it){   cout << endl ;}

template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
    cerr << *it << " = " << a << ' ' ;
    err(++it, args...);
}
int ini(){int x; scanf("%d",&x);return x;}
long long inl(){ long long x;scanf("%lld",&x); return x;}
double ind(){double x; scanf("%lf",&x);return x;}
#define Iin ini();
#define Lin inl();
#define Din ind();

int set_1(int n,int pos){return n = (n | (1<<pos));}
int reset_0(int n,int pos){return n= n & ~(1<<pos);}
bool check_bit(int n,int pos){return n = n & (1<<pos);}

int dx[8]= {1,0,-1,0,-1,-1,1,1};
int dy[8]= {0,1,0,-1,-1,1,-1,1};
const int N = (int) 1e6 + 5;
const int M = (int) 1e9 + 7;
const double pi=2* acos(0.0);

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //ios_base::sync_with_stdio(false); 
    //cin.tie(NULL);  

    int t=1,te=0;
    while(t--){
        string s,t;
        cin>>s>>t;
        int res=0;
        for(int i=0;i<3;i++){
            if(s[i]==t[i]){
                res++;
            }
        }
        cout<<res<<endl;

        //printf("Case %d: ",++te);
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){

  int n,k;
  bool ans = false;
  cin >> n >> k;
  if(n%2==0){ if(n/2 >= k) { ans = true;}} 
  else if(n%2 != 0) { if((n+1)/2 >= k) { ans=true;}}
            
  if (ans) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}

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

const int N=20;

int n,a[N],x,y,ans;
vector <pair <int,int>> v[N];

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		for(int j=0;j<a[i];j++)
		{
			scanf("%d%d",&x,&y);
			v[i].push_back({--x,y});
		}
	}

	for(int mask=0;mask<(1<<n);mask++)
	{
		bool ok=true;
		for(int i=0;i<n and ok;i++)
		{
			if(!(mask&(1<<i))) continue;
			for(auto p:v[i])
				if(bool(mask&(1<<p.first))!=p.second) ok=false;
		}

		if(ok) ans=max(ans,__builtin_popcount(mask));
	}

	printf("%d",ans);
}

Measured memory_bytes: 3796
#include <algorithm>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
constexpr ll INF = 1ll << 55;

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

// multi-dimensional vector (require c++14)
template <typename T, typename U>
static inline vector<U> make_nd_vector(T &&n, U &&val) noexcept {
  static_assert(is_integral<T>::value,
                "[make_nd_vector] 1st argument must be an integer type");
  return vector<U>(forward<T>(n), forward<U>(val));
}
template <typename T, typename... Args>
static inline decltype(auto) make_nd_vector(T &&n, Args &&... args) noexcept {
  static_assert(is_integral<T>::value,
                "[make_nd_vector] 1st argument must be an integer type");
  return vector<decltype(make_nd_vector(forward<Args>(args)...))>(
      forward<T>(n), make_nd_vector(forward<Args>(args)...));
}
//
// Print from Iterator
template <typename ite>
void print_ite(ite start, ite end, char sp = ' ', char en = '\n') {
  for (auto i = start; i != end; i++)
    cout << *i << sp;
  cout << en;
}
//
inline void Yes(bool condition) { cout << (condition ? "Yes\n" : "No\n"); }

int main() {
  char alpha;
  cin >> alpha;
  if (alpha >= 'a')
    cout << 'a' << endl;
  else
    cout << 'A' << endl;
}


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

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    // rdfile("_input.txt");

    int N, X;
    cin >> N >> X;

    long long D = 0;
    int cnt = 1;

    int L;
    for (int i=0; i<N; ++i) {
        cin >> L;
        D += L;
        if (D <= X) cnt ++;
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 384
#include<math.h>
#include<map>
#include<iostream>
#include <algorithm>
#include <string>
#include<vector>
#include<array>
#include<tuple>
#include<queue>
#include<stack>
#include<iomanip>
#include<bitset>
//AtCoderC++.cpp

using namespace std;

vector<int> _prime;
vector<int> build_prime_table(int max) {
	vector<int> table = vector<int>(max + 1, -1);
	table[0] = 0;
	table[1] = 0;
	table[2] = 1;
	for (int i = 3; i <= max; i++) {
		if (i % 2 == 0) { table[i] = 0; continue; }
		if (table[i] != -1)continue;
		table[i] = 1;
		for (int j = i + i; j <= max; j += i) {
			table[j] = 0;
		}
	}
	return table;
}

inline int ceileing(int a, int b) {
	return a % b == 0 ? a / b : a / b + 1;
}


vector<long long> comb = vector<long long>(100 * 100, -1);

long long combination(long long n, long long r) {
	if (n == 1 || n == 0)return 1;
	if (n == r)	return 1;
	else if (r == 0)return 1;
	else if (r == 1)return n;
	else if (comb[100 * (n - 1) + (r - 1)] != -1) return comb[100 * (n - 1) + (r - 1)];
	else {
		auto res = combination(n - 1, r - 1) + combination(n - 1, r);
		comb[100 * (n - 1) + (r - 1)] = res;
		return res;
	}
}

inline int count(int b, int N, int K) {
	int res = 0;
}

int main() {
	long long N, K; cin >> N >> K;
	if (K == 0) {
		cout << static_cast<long long>(N * N) << endl;
		return 0;
	}
	long long answer = 0;
	for (size_t b = K + 1; b <= N; b++) {
		int end = N % b;
		if (end < K || end == b - 1) {
			answer += ((N - K) / b + 1)*(b - K);
		} else {
			answer += ((N - K) / b + 1)*(end - K + 1);
			answer += ((N - K) / b)*(b - end - 1);
		}
	}
	cout << answer << endl;
}

Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main()
{
    int a,b,c,d,g;
    while(scanf("%d",&g)!=-1)
    {
        a=g/1000;
        b=(g/100)%10;
        c=(g%100)/10;
        d=g%10;
          if((a+b+c+d)==7){printf("%d+%d+%d+%d=7",a,b,c,d); continue;}
          if((a-b+c+d)==7){printf("%d-%d+%d+%d=7",a,b,c,d); continue; }
          if((a+b-c+d)==7){printf("%d+%d-%d+%d=7",a,b,c,d); continue;}
          if((a+b+c-d)==7){printf("%d+%d+%d-%d=7",a,b,c,d); continue;}
          if((a-b-c+d)==7){printf("%d-%d-%d+%d=7",a,b,c,d); continue;}
          if((a-b+c-d)==7){printf("%d-%d+%d-%d=7",a,b,c,d); continue; }
          if((a+b-c-d)==7){printf("%d+%d-%d-%d=7",a,b,c,d); continue;}
          if((a-b-c-d)==7){printf("%d-%d-%d-%d=7",a,b,c,d); continue; }


    }
    return 0;
}

Measured memory_bytes: 128
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

a, b = na()

print((a + b) % 24)

Measured memory_bytes: 3064
X=int(input())

C=[0]
for i in range(1,64):
    C.append(pow(i,5))

c=0
ans1=0
ans2=0
while c<=X:
    temp=X-c
    if temp in C:
        ans2=C.index(temp)
        print(ans1,-ans2)
        break
    else:
        ans1+=1
        c=C[ans1]
else:
    for j in range(64,120):
        C.append(pow(j,5)) 
    #print(len(C))
    c=0
    ans1=0
    ans2=0
    for k in range(120):
        if C[k]>=X:
            for l in range(k):
                if C[k]-C[l]==X:
                    print(k,l)
                    break
            else:
                continue
            break


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

int main()
{
    int a[5];
    for (int i = 0; i < 5; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < 5; i++)
    {
        if (a[i] == 0)
        {
            cout << i + 1 << "\n";
            break;
        }
    }
}

Measured memory_bytes: 3576
import numpy as np
a,b,h,m = map(int,input().split())

t1 = 2 * np.pi * m /60

t2 = 2 * np.pi * ( 60*h+m)/(60*12)

print(np.sqrt(a**2 + b**2 - 2*a*b*np.cos(t2-t1)))

Measured memory_bytes: 27216
def choose(n, r, mod)
  return 0 if not (0 <= r and r <= n)
  return 1 if r == 0 or r == n
  fact(n, mod) * inverse(fact(r, mod) * fact(n-r, mod) % mod, mod) % mod
end
@fact = [1]
def fact(n, mod)
  if n > @fact.size then
    f = @fact[-1]
    (@fact.size+1..n).each{|i|
      f = (f * i) % mod
      @fact << f
    }
  end
  @fact[n-1]
end
def inverse(x, mod)
  pow(x, mod-2, mod)
end
def pow(x, n, mod)
  ans = 1
  while n > 0
    ans = ans * x % mod if n.odd?
    x = x * x % mod
    n >>= 1
  end
  ans
end

H, W, A, B = gets.chomp.split(" ").map(&:to_i)
MOD = 10 ** 9 + 7

ans = choose(H+W-2, H-1, MOD)
X = W-B-1
d = (H-A+1..H).inject(0){|r, h|
  (r + choose(h+B-2, h-1, MOD) * choose(H-h+X, X, MOD)) % MOD
}

ans -= d
ans += MOD if ans < 0
puts ans


Measured memory_bytes: 3452
#include <climits>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

void dijkstra(vector<vector<pair<int, int>>>& g, vector<int>& weights) {
    int n_vertex = weights.size();
    vector<bool> visited(n_vertex, false);
    weights[0] = 0;
    while (true) {
        int min_idx;
        int min_weight = INT_MAX;
        for (int i = 0; i < n_vertex; ++i) {
            if (!visited[i] && weights[i] < min_weight) {
                min_idx = i;
                min_weight = weights[i];
            }
        }

        if (min_weight == INT_MAX)
            break;

        visited[min_idx] = true;

        for (int i = 0; i < g[min_idx].size(); ++i) {
            int adj = g[min_idx][i].first;
            int weight_via_idx = weights[min_idx] + g[min_idx][i].second;
            if (!visited[adj] && weight_via_idx < weights[adj]) {
                weights[adj] = weight_via_idx;
            }
        }
    }
}

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

    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < n; ++i) {
        int u, k;
        cin >> u >> k;
        for (int j = 0; j < k; ++j) {
            int v, c;
            cin >> v >> c;
            g[i].push_back(make_pair(v, c));
        }
    }

    vector<int> weights(n, INT_MAX);
    dijkstra(g, weights);
    for (int i = 0; i < n; ++i)
        cout << i << ' ' << weights[i] << '\n';
}



Measured memory_bytes: 3124
//============================================================================
// Name        : JOI.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <stdio.h>
using namespace std;
typedef long long ll;
int N;
int C[501];
int S[501];
int F[501];
int main(){
	cin>>N;
	for(int i=1;i<N;i++){
		cin>>C[i]>>S[i]>>F[i];
	}
	ll T=0;
	for(int i=1;i<N;i++){
		T=S[i]+C[i];
		for(int j=i+1;j<N;j++){
			if(T<=S[j]){
				T+=S[j]-T+C[j];
			}else{
				if((T-S[j])%F[j]==0){
					T+=C[j];
				}else{
					T+=(-(T-S[j])%F[j])+F[j]+C[j];
				}
			}

		}
		cout<<T<<endl;

	}


	cout<<0<<endl;




    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, x, m[1001], m2 = 0, mi, result;
  cin >> n >> x;
  for (int i = 0; i < n; i++) {
    cin >> m[i];
    m2 += m[i];
    if (i == 0) {
      mi = m[0];
    } else if (mi > m[i]) {
      mi = m[i];
    }
  }
  x -= m2;
  result = n + (x / mi);
  cout << result << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cctype>
#include<string>

std::string toUpper(std::string s){
	for(int i=0; i < s.size(); i++){
		s[i] = toupper(s[i]);
	}
	return s;
}

std::string clearSt(std::string s){
	int counter = 0;
	std::string cleared = s;
	for(int i = 0; i< s.size(); i++){
		if (isalpha(s[i])){
			cleared[counter] = s[i];
			counter +=1;
		}
	}
	cleared = cleared.substr(0, counter);
	return cleared;
}

int main(void){
	
	std::string W, st;
	int count = 0;
	
	std::cin >> W;
	W = toUpper(W);
	//std::cout  << W << std::endl;
	
	while(1){
		std::cin >> st;
		if(st == "END_OF_TEXT") break;
		st = toUpper(st);
		st = clearSt(st);
		//std::cout << st << std::endl;
		if(st == W) count += 1;
		//std::cout << "count is "  << count << std::endl;
	}
	
	std::cout << count << std::endl;
	
	return 0;
}

Measured memory_bytes: 1200
#include<bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef ONLINE_JUDGE
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long long ll;
typedef pair<int,int> pie;
const int inf = 1e9+7;
int main() {
	int n,m,x;
	cin >> n >> m >> x;
	vector<vector<int>> a(n,vector<int> (m));
	vector<int> cost(n);
	for(int i=0;i<n;i++) {
		for(int j=0;j<=m;j++) {
			if(!j) cin >> cost[i];
			else cin>> a[i][j-1];
		}
	}
	//cout<<"got";
	//debug()<<imie(cost);
	int base = pow(2,n)-1;
	//debug()<<imie(base);
	int bestYet = inf;
	for(int mask = 0; mask<=base; ++mask) {
		int thisone =  0;
		vector<int> skills(m,0);
		for(int i=0;i<n;++i) {
			if(1 & (mask >> i)) {
				thisone += cost[i];
				for(int j=0;j<m;j++) {
					skills[j]+=a[i][j];
				}
			}
		}
		bool ok = 1;
		for(auto it:skills) {
			if(it < x) {
				ok = 0;
				break;
			}
		}
		//debug()<<imie(ok) imie(skills) imie(bitset<12>(mask).to_string());
		if(ok) bestYet = min(bestYet, thisone);
	}
	cout<<(bestYet==inf?-1:bestYet);
}


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

int main(){
	typedef long long Int;
	
	const int MAX_N = 100;
	int N, A[MAX_N];
	Int table[MAX_N][21];//i番目までの数字を用いてjを作るときに、何通りあるかを、でtable[i][j]表現する
	
	scanf("%d", &N);
	for(int i = 0; i < N; i++){
		scanf("%d", A + i);
	}
	
	table[0][A[0]] = 1;
	for(int i = 1; i < N; i++){
		for(int j = 0; j <= 20; j++){
			table[i][j] = ((j - A[i] >= 0)? table[i - 1][j - A[i]] : 0) + ((j + A[i] <= 20)? table[i - 1][j + A[i]] : 0);
		}
	}
	
	printf("%lld\n", table[N - 1][0]);
	
	return 0;
}

Measured memory_bytes: 1044
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  ll x,y;
  cin>>x>>y;

  ll ans=0;
  if(x==0&&y>0){
    cout<<y<<endl;
    return 0;
  }else if(x==0&&y<0){
    cout<<abs(y)+1<<endl;
    return 0;
  }else if(x<0&&y==0){
    cout<<abs(x)<<endl;
    return 0;
  }else if(x>0&&y==0){
    cout<<x+1<<endl;
    return 0;
  }

  if(x<y){
    if(x>=0) ans=y-x;
    else{
      if(y<=0) ans=y-x;
      else{
        if(abs(x)<=y) ans=y-abs(x)+1;
        else ans=abs(x)-y+1;
      }
    }
  }else if(x>y){
    if(y>=0) ans=x-y+2;
    else{
      if(x<0) ans=x-y+2;
      else{
        if(abs(y)<=x) ans=x-abs(y)+1;
        else ans=abs(y)-x+1;
      }
    }
  }

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


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

# from collections import defaultdict
# d = defaultdict(list)

# from itertools import combinations
# comb = combinations(range(N), 2)

# 累積和
# from itertools import accumulate
# _list = list(accumulate(a_list)

# from functools import lru_cache
# @lru_cache(maxsize=None)
# def setUp(self):
#     dp.cache_clear()


# factのstartを指定しとけば, 計算量O(k)になる
def comb(n, k, mod):
    a = factmod(n, n - k + 1, mod)
    b = factmod(k, 1, mod)

    div = pow(b % mod, mod - 2, mod)  # フェルマーの小定理

    return a * div % mod


def factmod(n, start, mod):
    val = 1
    for i in range(start, n + 1):
        val *= i
        val %= mod
    return val


def resolve():
    global dp

    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    # N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    n, a, b = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    # h_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    # grid = [[int(x) for x in sys.stdin.readline().split()]
    #         for _ in range    (N)]  # int grid

    mod = 10**9 + 7
    print(int((pow(2, n, mod) - 1 - comb(n, a, mod) - comb(n, b, mod)) % mod))


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 1 3"""
        output = """7"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """1000000000 141421 173205"""
        output = """34076506"""
        self.assertIO(input, output)


Measured memory_bytes: 5592
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
using namespace std;
const int maxn = 2e5+10;

int read(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-48;c=getchar();}
	return x*f;
}

int k,m,n;
int num[maxn],a[maxn];
int main(){
	n=read();
	for(register int i=1;i<=n;i++){
		a[i]=read();
		num[a[i]]++;
	}
	long long ans=0;
	for(register int i=1;i<=n;i++){
		ans+=1ll*(num[i]-1)*num[i]/2;
	}
	for(register int i=1;i<=n;i++){
		long long anss=ans-num[a[i]]+1;
		printf("%lld\n",anss);
	}
	return 0;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define rep(I, N) for (int I = 1; I <= (N); ++I)
#define repp(I, N) for (int I = 0; I < (N); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORR(I, A, B) for (int I = (A); I >= (B); I--)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
const int N = 2e5 + 5;
const double eps = 1e-7;
const int mod = 1e9 + 7;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
int a[N];
int main() {
    int n;
    cin >> n;
    rep(i,n) cin >> a[i];
    int minn = 1e9;
    rep(i,n - 1)
    {
        int sum1 = 0;
        int sum2 = 0;
        rep(j,i) sum1 += a[j];
        FOR(j,i + 1,n) sum2 += a[j];
        minn = min(minn, abs(sum1 - sum2));
    }
    cout << minn << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int M = 1e9 + 7;

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

  int n;
  cin >> n;

  int a[n][n];
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cin >> a[i][j];
    }
  }
  
  vector<int> dp(1<<n, 0);
  dp[0] = 1;
  for (int i = 0; i < n; ++i) {
    vector<int> tmp(1<<n, 0);
    for (int j = 0; j < (1<<n); ++j) {
      if (__builtin_popcount(j) != i + 1) continue;
      for (int b = 0; b < n; ++b) {
        if (a[i][b] && (j>>b)&1) {
          tmp[j] = (tmp[j] + dp[j^(1<<b)]) % M;
        }
      }
    }
    swap(tmp, dp);
  }
  cout << dp[(1<<n)-1] << '\n';
}


Measured memory_bytes: 19740
import java.io.*;
import java.util.*;
 
public class Main{
    public static void main(String[] args){
          Scanner sc = new Scanner(System.in);
      		long D = sc.nextInt(),T = sc.nextInt(),S = sc.nextInt();
      		if ((D-T*S)>0){
              System.out.println("No");
            }else{
              System.out.println("Yes");
            }
      
              
    }
}

Measured memory_bytes: 35624
#include<iostream>
#include<cstdio>
using namespace std;
int a,b,s1,s2,s3,ans;

int main(){
	scanf("%d%d",&a,&b);
	s1=a+b;
	s2=a-b;
	s3=a*b;
	ans=max(max(s1,s2),s3);
	printf("%d\n",ans);
}

Measured memory_bytes: 256
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb       push_back
#define sz(x)    ((int)(x.size()))
#define all(x)   x.begin(),x.end()
#define clr(x)   memset(x,0,sizeof x)
const int inf = ( 1953125 << 9 );
const int maxn = 2 * 1e5 + 5;
bool vis[maxn];


int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	freopen("input.in", "r", stdin); //freopen("output.txt", "w", stdout);
	clr(vis);

	ll a,b,x,y;
	cin>>a>>b>>x>>y;
	int arr1[a],arr2[b];
	for(auto &it : arr1)cin>>it;
	for(auto &it : arr2)cin>>it;
	sort(arr1, arr1+a);
	sort(arr2, arr2+b);

	for (int i = arr1[a-1]+1; i <= arr2[0]; ++i) {
		if(i > x && i <= y)
			if(i > arr1[a-1] && i <= arr2[0])
				return cout<<"No War", 0;
	}
	cout<<"War";

}


Measured memory_bytes: 512
import java.util.Scanner;

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

        while(true){
            int H = sc.nextInt();
            int W = sc.nextInt();
            if(H == 0 && W == 0) break; 
            
            for(int i = 0; i < H; i++){
                for(int j = 0; j < W; j++){
                    if(i != 0 && i != H-1 && j != 0 && j != W-1)System.out.print(".");
                    else System.out.print("#");
                }
                System.out.println();
            }

            System.out.println();
        }

        sc.close();
    }
}


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

int main(){
	vector<bool> pro(100001,false);
	for(int i=0;i<6;i++){
		pro.at(100+i)=true;
	}
	for(int i=200;i<=100000;i++){
		for(int j=0;j<6;j++){
			if(pro.at(i-100-j)){
				pro.at(i)=true;
				break;
			}
		}
	}
	
	int X;
	cin >> X;
	if(pro.at(X)){
		cout<<"1"<<endl;
	}
	else{
		cout<<"0"<<endl;
	}
}


Measured memory_bytes: 256
import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
read = sys.stdin.read

N, *ab = map(int, read().split())
a, b = zip(*zip(*[iter(ab)] * 2))

graph = csr_matrix(([1] * (N - 1), (a, b)), shape=(N + 1, N + 1))
distance = dijkstra(graph, directed=False, indices=[1, N])
d1 = distance[0][1:]
dn = distance[1][1:]

Fennec = np.count_nonzero(d1 <= dn)

if Fennec > N - Fennec:
    print('Fennec')
else:
    print('Snuke')

Measured memory_bytes: 36808
#include<iostream>
#include<string>
using namespace std;
int main(){
  string S,T;
  cin>>S>>T;
  bool flag=0;
  for(size_t i=0;i<=S.length()-1;i++){
  
    flag=1;
    for(size_t j=i;j<=i+S.length()-1;j++){
      
        if(S[j%S.length()]!=T[j-i]){
          
          flag=0;
          break;
        }
    }
    if(flag==1){
      
      cout<<"Yes";
      return 0;
    }
  }
  cout<<"No";
  return 0;
}

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

using namespace std;
using ll=long long;

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

int main(){
  cin.tie(nullptr);ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  ll n,k;cin>>n>>k;
  ll m=n%k;
  cout<<min(m,k-m)<<endl;
}


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

using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1LL<<60;

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

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

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

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

  int n;
  cin >> n;
  vector<ll> a(n);

  rep(i, n) cin >> a[i];

  sort(a.rbegin(), a.rend());
  ll ans = -1e17;
  if(n % 2 == 1){

    ll tans = 0;
    ll cnt = 0;
    rep(i, n/2-1){
      tans += 2 * a[cnt];
      cnt++;
    }
    tans += a[cnt];
    cnt++;
    tans += a[cnt];
    cnt++;
    rep(i, cnt, n){
      tans += -2 * a[i];
    }

    chmax(ans, tans);

    tans = 0;
    cnt = 0;
    rep(i, n/2){
      tans += 2 * a[cnt];
      cnt++;
    }
    tans += -1 * a[cnt];
    cnt++;
    tans += -1 * a[cnt];
    cnt++;
    rep(i, cnt, n){
      tans += -2 * a[i];
    }

    chmax(ans, tans);

  }else{

    ll tans = 0;
    int cnt = 0;
    rep(i, n/2-1){
      tans += 2 * a[i];
      cnt++;
    }
    tans += a[cnt];
    cnt++;
    tans += -a[cnt];
    cnt++;
    rep(i, cnt, n){
      tans += -2 * a[i];
    }

    chmax(ans, tans);


  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <bitset>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <regex>
#include <iomanip>
#include <climits>
#include <utility>
#include <queue>
using namespace std;
using ll = long long int;
using dd = long double;
const ll MOD = 1e9 + 7;
const dd PI = 3.1415926435;

class UnionFind
{
public:
    UnionFind(int N) : par(N)
    {
        for (ll i = 0; i < N; i++)
        {
            par[i] = i;
        }
    }

    int root(int x)
    {
        if (par[x] == x)
            return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y)
    {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry)
            return;
        par[rx] = ry;
    }

    bool same(int x, int y)
    {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

private:
    vector<int> par;
};

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

ll fact(ll n)
{
    if (n == 0)
    {
        return 1;
    }
    if (n == 1)
    {
        return 1;
    }
    return n * fact(n - 1) % MOD;
}

ll pow_fast(ll n, ll k)
{
    if (k == 0)
    {
        return 1;
    }
    if (k == 1)
    {
        return n;
    }

    if (k % 2 == 0)
    {
        ll tmp = pow_fast(n, k / 2LL);
        return tmp * tmp % MOD;
    }
    else
    {
        ll tmp = pow_fast(n, k / 2LL);
        tmp *= tmp;
        tmp %= MOD;
        return tmp * n % MOD;
    }
}

map<ll, ll> sosuu(ll n)
{
    map<ll, ll> res;
    for (ll i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            res[i] += 1;
            n /= i;
        }
    }
    if (n != 1)
    {
        res[n] += 1;
    }
    return res;
}

struct Dish
{
    ll time;
    ll taste;
};
int main()
{
    ll N;
    cin >> N;
    ll D, X;
    cin >> D >> X;

    ll sum = 0;
    for (ll i = 0; i < N; i++)
    {
        ll ai;
        cin >> ai;
        sum += ((D - 1) / ai + 1);
    }
    cout << (sum + X) << endl;
    
}

Measured memory_bytes: 3604
A,B,C,X = [int(input()) for i in range(4)]
cnt = 0

for a in range(A + 1):
    for b in range(B + 1):
        for c in range(C + 1):
            total = 500*a + 100*b + 50*c
            if total == X:
                cnt += 1
print(cnt)

Measured memory_bytes: 3060
"""
dp[i][j][k] => i行目、j列のマスまで見る。k個取る時の最高値。
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

    dp = [[0]*4 for _ in range(C)]

    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i == 0 and j == 0 and v != 0:
                dp[j][1] = v
                continue
            
            if i != 0:
                #上から降りてくる場合の価値を求める
                #i行目j列のアイテムを取らない場合
                dp[j][0] = max(dp[j])
                #i行目j列のアイテムを取る場合
                if v!=0:
                    dp[j][1] = dp[j][0] + v

            #左から入ってくる場合の価値を求める
            if j != 0:
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v == 0:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k],dp[j-1][k-1]+v)
    print(max(dp[-1]))
main()

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

using namespace std;
const int maxn = 1e5 + 10;
const int INF = 2e9 + 10;
int n;
int arr[105];
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    for(int i = 0; i < n; i ++){
        cin >> arr[i];
    }
    int ret = -INF;
    for(int i = 0; i < n; i ++){
        for(int j = i + 1; j < n; j ++){
            ret = max(ret, abs(arr[i] - arr[j]));
        }
    }
    cout << ret << endl;
    return 0;
}


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

int main() {
  int n;
  cin >> n;
  vector<ll> cnt(100002);
  rep(i,n){
    int a;
    cin >> a;
    cnt[a] ++;
  }
  ll sum=0;
  rep(i,100002) sum+=i*cnt[i];
  int q;
  cin >> q;
  rep(i,q){
    int b, c;
    cin >> b >> c;
    sum -= b*cnt[b];
    sum -= c*cnt[c];
    cnt[c] += cnt[b];
    cnt[b] = 0;
    sum += c*cnt[c];
    cout << sum << endl;
  }
}


Measured memory_bytes: 4032
/*
    AUTHOR : TANMAY SINHA
    INORMATION TECHNOLOGY
    BIT MESRA ,RANCHI
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ld long double
#define ull unsigned long long int
#define ll long long int
#define pb(x) push_back(x)
#define eb(x) emplace_back(x)
#define mp make_pair
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
#define rep(j,L,R) for(j=L;j<R;j++)
#define per(i,L,R) for(i=L;i>= R;i--)
#define all(con) (con).begin(),(con).end()
#define fi first
#define se second
#define foreach(iter,con) for(auto iter=(con).begin(); iter!=(con).end(); iter++)
#define DEBUG
#ifdef DEBUG
#define deb2(args...) {dbg,args; cerr<<endl;}
#else
#define deb2(args...)
#endif
struct debb{template<typename T> debb& operator,(const T &v){cerr<<v<<" ";return *this;}}dbg;
#define deb1(args...) do {cerr << #args << " : "; dbg,args; cerr << "\n";} while(0)
#define printa(a,L,R) rep(i,L,R) cout << a[i] <<' ';cout<<"\n";
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
template<typename T>T gcd(T a,T b){if(b==0)return a;else return gcd(b,a%b);}
template<typename T>T lcm(T a,T b){return a/gcd(a,b)*b;}
ll power(ll x,ll y,ll p){ll res=1;x=x%p;while(y>0){if(y&1)res=((res%p)*(x%p))%p;y=y>>1;x=(x*x)%p;}return res;}
ll pow1(ll x,ll y){ll res=1;while(y>0){if(y&1)res=(res*x);y=y>>1;x=x*x;}return res;}
const ll INF = 1e18l+10,N = 1e5+10,MAX = 1e6+5;

int main()
{
   SPEED
   ll r;
   cin>>r;
   cout<<r*r<<"\n";
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> l(n),r(n);
  for(Int i=0;i<n;i++) cin>>l[i]>>r[i];

  multiset<Int> L,R;
  L.emplace(l[0]);
  R.emplace(l[0]);

  Int dL=0,dR=0,dH=0;

  for(Int i=1;i<n;i++){
    dL-=r[i]-l[i];
    dR+=r[i-1]-l[i-1];
    auto latte=--L.end();
    auto malta=R.begin();

    if(l[i]<dL+*latte){
      dH+=-(l[i]-(dL+*latte));
      R.emplace(dL+*latte-dR);
      L.erase(latte);
      L.emplace(l[i]-dL);
      L.emplace(l[i]-dL);
    }else if(dR+*malta<l[i]){
      dH+=(l[i]-(dR+*malta));
      L.emplace(dR+*malta-dL);
      R.erase(malta);
      R.emplace(l[i]-dR);
      R.emplace(l[i]-dR);
    }else{
      L.emplace(l[i]-dL);
      R.emplace(l[i]-dR);
    }
    if(0){
      cout<<i<<":"<<dH<<endl;
      cout<<"L:";
      for(Int a:L) cout<<a+dL<<" ";
      cout<<endl; 
      cout<<"R:";
      for(Int a:R) cout<<a+dR<<" ";
      cout<<endl;
    }
  }

  cout<<dH<<endl;
  return 0;
}


Measured memory_bytes: 11136
using System;
class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int b = int.Parse(input[0]);
        int c = int.Parse(input[1]);
        int d = int.Parse(input[2]);
        Console.WriteLine(b * c / 2);

    }
}

Measured memory_bytes: 11092
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	string s; cin>>s;
	if(s[2]==s[3] && s[4]==s[5]){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}


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

using namespace std;

const int maxn=100005;

int n,k;
char x[maxn];
vector<pair<int,int> > v;

int main(){
	cin>>n>>k;
	cin>>(x+1);
	int curl=1;
	for(int i=2;i<=n+1;i++){
		if(x[i]!=x[i-1]||i==n+1){
			v.push_back(make_pair(curl,x[i-1]));
			curl=1;
		} else curl++;
	}
	cout<<min(n-1,n-(int)v.size()+k*2);
	return 0;
} 

Measured memory_bytes: 1528
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
color = [list(map(int, input().split())) for _ in range(N)]

cs = [[0]*C for _ in range(3)]
for i in range(N):
  for j in range(N):
    amari = (i+j)%3
    cs[amari][color[i][j]-1] += 1

ans = 500*500*1000
for i in range(C):
  for j in range(C):
    if i == j:
      continue
    for k in range(C):
      if (i==k) or (j==k):
        continue
      now = 0
      for ci in range(C):
        now += D[ci][i] * cs[0][ci]
        now += D[ci][j] * cs[1][ci]
        now += D[ci][k] * cs[2][ci]
          
      ans = min(ans, now)
      
print(ans)


Measured memory_bytes: 5620
from collections import deque
N, Q = map(int, input().split())
brunch = [[] for _ in range(N)]
value = [0 for _ in range(N)]
 
for _ in range(N-1):
  a, b = map(int, input().split())
  brunch[a-1].append(b-1)
  brunch[b-1].append(a-1)
  
for _ in range(Q):
  f, val = map(int, input().split())
  value[f-1] += val
 
d = deque()
d.append((0, -1))
while len(d):
  root, from_root = d.popleft()
  for to in brunch[root]:
    if to == from_root:
      continue
    value[to] += value[root]
    d.append((to, root))
print(' '.join(map(str, value)))

Measured memory_bytes: 65672