akhauriyash/Code-Regression huggingface dataset:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    N=n*(n+1)//2

    if(sum(A)%N):
        print("NO")
        return

    k=sum(A)//N
    for i in range(n):
        q,r=divmod(k-(A[(i+1)%n]-A[i]),n)
        if(q<0 or r):
            print("NO")
            return

    print("YES")
resolve()

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

using namespace std;

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

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int main(){
  int a,b,c;
  cin>>a>>b>>c;
  cout << min(c, b/a) << endl;
  return 0;
}


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


typedef long long ll;
typedef pair<int, int> P;

struct edge {int to; ll cost; };

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

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

ll LCM(ll a, ll b){
  if(a<b) swap(a,b);
  return a/GCD(a,b)*b;
}

int main(){
  int n;
  cin >> n;
  ll L[n]={};
  int ans = 0;
  for(int i=0; i<n; i++) cin >> L[i];
  for(int i=0; i<n-2; i++){
    for(int j=i+1; j<n-1; j++){
      for(int k=j+1; k<n; k++){
        if(L[i]==L[k] || L[i]==L[j] || L[j]==L[k]) continue;
        ll s = L[i]+L[j]+L[k];
        ll m = max(L[i], L[j]);
        m = max(m, L[k]);
        s -= 2*m;
        if(s>0) ans++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3592
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		sc.close();
		
		int ans = 700;
		for(int i = 0;i < S.length();++i)
			if(S.charAt(i) == 'o')
				ans += 100;
		System.out.println(ans);
	}
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

ll n;
ll a[101010];
map<ll,ll> pre,suf;
ll d=0;
vector<ll> res;

int main(){
  cin>>n;
  rep(i,n)cin>>a[i];
  rep(i,(n/2)){
    d-=abs(pre[a[i]]-suf[a[i]]);
    pre[a[i]]++;
    d+=abs(pre[a[i]]-suf[a[i]]);

    d-=abs(pre[a[n-1-i]]-suf[a[n-1-i]]);
    suf[a[n-1-i]]++;
    d+=abs(pre[a[n-1-i]]-suf[a[n-1-i]]);
    if(d==0){
      res.push_back(i+1);
      if(i+1!=n-1-i)res.push_back(n-1-i);
    }
  }
  res.push_back(n);
  sort(all(res));
  uni(res);
  cout<<res[0];
  repl(i,1,res.size())cout<<" "<<res[i];
  cout<<endl;
  return 0;
}




Measured memory_bytes: 10204
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef vector<int>Vl;
typedef pair<int,int>pii;
typedef vector<pii>Vll;
typedef vector<pair<int,pair<int,int> > >Vlll;
#define S second
#define F first
#define mp make_pair
#define ms(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define sl(n) cin>>n 
#define pl(n) cout<<n<<" "
const int Nx=1e5+2;
const int mod=998244353;
const int inf=(int)(1e9+10LL);
const double pI=6.28318530717958623200;

void solve()
{
	int R;
	sl(R);
	cout<<pI*R;

  
}

signed main(){
  int test=1;
 // sl(test);
 while(test--){
 	solve();
 }
 
}

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

int main(){
	int n;
	scanf("%d", &n);
	int arrayb[100];
	for(int i=0; i<n-1; i++){
		scanf("%d", &arrayb[i]);
	}
	
	int answer=0;
	answer+= arrayb[0];
	int ser=0;
	for(int i=0; i<n-2; i++){
		if(arrayb[i]<arrayb[i+1]) ser=arrayb[i];
		else ser=arrayb[i+1];
		answer+=ser;
	}
	answer+=arrayb[n-2];
	
	printf("%d", answer);
	
	
	return 0;
}

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

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

    int sum = 0;
    for (unsigned i = 0; i < n.size(); ++i)
        sum += (int)(n[i] - '0');
    if (sum % 9)
        cout << "No";
    else
        cout << "Yes";
}


Measured memory_bytes: 3720
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repb(i, n) for (int i = (n-1); i >= 0; i--)
#define rea(i, a, b) for (int i = (a); i < (b); i++)
#define reab(i, a, b) for (int i = (a)-1; i >= (b); i--)
#define ALL(a) (a).begin(),(a).end()
#define SZ(x) ((int)(x).size())
#define PRINT(V) for (auto v:(V)) {cerr << v << " ";} cerr << endl
#define dump(x) cerr << #x << " : " << (x) << endl
#define dump2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")" << endl
inline ll GCD(ll a, ll b){return b ? GCD(b, a % b) : a;}
inline ll divceil(ll a, ll b){return (a+b-1) / b;}
const int MOD = 1000000007;
/* END OF TEMPLATE */

// http://drken1215.hatenablog.com/entry/2018/06/08/210000
const int MAX = 200010;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
    COMinit();
    ll n, m, k;
    cin >> n >> m >> k;
    ll ansn = 0, ansm = 0, ans;
    ll anstemp = 0;
    ll m2 = m*m % MOD;
    ll n2 = n*n % MOD;
    rea(i, 1, n){
        anstemp = (n-i) * COM(n*m-2, k-2) % MOD;
        anstemp = anstemp * i % MOD;
        ansn = (ansn + anstemp) % MOD;
    }
    ansn = ansn * m2 % MOD;
    rea(i, 1, m){
        anstemp = (m-i) * COM(n*m-2, k-2) % MOD;
        anstemp = anstemp * i % MOD;
        ansm = (ansm + anstemp) % MOD;
    }
    ansm = ansm * n2 % MOD;
    ans = (ansn + ansm) % MOD;
    cout << ans << endl;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
typedef int int__;
#define int long long
#define pb push_back
#define pi pair<int,int>
#define vpi vector<pi>
#define vi vector<int>
#define vvi vector<vi>
#define fi first
#define se second
#define forn(i, n)for(int i=0;i<int__(n);i++) 
#define sz(a)int__(a.size())
template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a){return out << "(" << a.first << ", " << a.second << ")";}
template<class A>ostream& operator<<(ostream& out,const vector<A>&v){out<<"[";forn(i,sz(v)){if(i)out<<", ";out<<v[i];}return out<<"]";}
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
const int mod = 1e9 + 7;
int Mod(int x){x%=mod;if(x<0)x+=mod;return x;}
int Pow(int x,int n){if(n==0)return 1;int t=Pow(x,n/2);t=Mod(t*t);if(n&1)t=Mod(t*x);return t;}
#define watch(x) cout << #x << " : " << x << endl;
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
#define all(x) x.begin(), x.end()

int__ main() {
	fast;

	int n,d,A; cin >> n >> d >> A;
	d = 2*d;

	vpi a(n);

	for(int i=0;i<n;i++) cin >> a[i].fi >> a[i].se;

	sort(all(a));

	int ans=0;

	vi c(n+1,0);

	int i=0,j=0;
	while(i < n) {
		
		while(j<n and a[j].fi - a[i].fi <= d) j++;

		int cur = max(0LL, a[i].se - c[i]*A);
		int t = cur/A;
		if(cur % A) t++;

		ans += t;

		c[i] += t;
		c[j] -= t;

		c[i+1] += c[i];
		i++;
	}

	cout << ans << endl;
}	

Measured memory_bytes: 4992
import java.io.*;
import java.util.*;

class Main
{

	static Scanner sc;

	public static void main( String[] args ) throws IOException
	{
		sc = new Scanner( new BufferedReader( new InputStreamReader( System.in ) ) );
	    int a = sc.nextInt(), b = sc.nextInt();
	    System.out.printf("%d %d\n", a * b, a + a + b + b);
	}
}


Measured memory_bytes: 26164
#include<iostream>
#include<list>
#define LL long long
using namespace std;
struct R{
	LL cost;
	LL st;
	LL id;
};

int main(){
	while (true){
		LL n;
		cin >> n;
		if (n == 0) break;
		list<R> storage;
		storage.emplace_back(R{1ll << 60, 0, -1});

		for (int i = 0; i < n; ++i){
			char command;
			cin >> command;
			if ('W' == command){
				LL l,s;
				cin >> l >> s;
				for (auto it = storage.begin(); it != storage.end(); ++it){
					if (it->id != -1) continue;
					if(it->cost - s > 0){
						auto cost = it->cost;
						auto st = it->st;

						it->cost = s;
						it->id = l;

						++it;
						storage.insert(it, R{ cost - s, st + s, -1 });
						break;
					}
					else{
						s -= it->cost;
						it->id = l;
						if (s == 0) break;
					}
				}
			}
			else if ('R' == command){
				LL p;
				cin >> p;

				for (auto it = storage.begin(); it != storage.end(); ++it){
					if (it->st <= p && it->st + it->cost > p){
						cout << it->id << endl;
					}
				}
			}
			else {
				LL l;
				cin >> l;

				for (auto it = storage.begin(); it != storage.end(); ++it){
					if(it->id==l) it->id = -1;
				}
			}
		}
		cout << endl;
	}


	return 0;
}

Measured memory_bytes: 1400
#include <stdio.h>

int main(void) {
  
  int A, B;
  scanf("%d %d", &A, &B);
  
  int total = 0;
  
  for(int i = 0; i < 2; ++i) {
    if(A > B) {
      total += A;
      --A;
    } else {
      total += B;
      --B;
    }
  }
  
  printf("%d\n", total);
  
  return 0;
  
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <float.h>
#include <iomanip>
#include <iostream>
using namespace std;

int main()
{
    char A,B;
    cin>>A>>B;

    if(A=='H'){
        cout << B<<endl;
    }else{
        if(B=='H'){
            cout<<'D'<<endl;
        }else{
            cout<<'H'<<endl;
        }

    }

    return 0;
}


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

bool isATCG(char c) {
  string S = "ATCG";
  bool isATCG = false;
  rep(i,S.size()) if(c==S[i]) isATCG = true; 
  return isATCG;
}

int main() {
  string S;
  cin >> S;
  int ans=0;
  int now=0;
  rep(i,S.size()) {
    if(isATCG(S[i])) now++;
    else now = 0;
    ans = max(ans, now);
  }
  cout << ans << endl;
}


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

typedef complex<double> Point, Vector;
typedef pair<Point, Point> Segment, Line;
typedef vector<Point> Polygon;

#define X real()
#define Y imag()
#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)

double dot(Vector a, Vector b){
    return a.X * b.X + a.Y * b.Y;
}

double cross(Vector a, Vector b){
    return a.X * b.Y - a.Y * b.X;
}

double norm(Vector a){
    return a.X * a.X + a.Y * a.Y;
}

double abs(Vector a){
    return sqrt(norm(a));
}

int contains(Polygon g, Point p){
    int n = g.size();
    bool x = false;
    for(int i=0; i<n; i++){
        Point a = g[i] - p;
        Point b = g[(i + 1) % n] - p;
        if(abs(cross(a, b)) < EPS && dot(a, b) < EPS) return 1;
        if(a.Y > b.Y) swap(a, b);
        if(a.Y < EPS && EPS < b.Y && cross(a, b) > EPS) x = !x;
    }

    return (x ? 2 : 0);
}

int main(){
    int g; cin>>g;
    Polygon poly;
    for(int i=0; i<g; i++){
        double a, b; cin>>a>>b;
        poly.emplace_back(a, b);
    }

    int n; cin>>n;
    for(int i=0; i<n; i++){
        double a, b; cin>>a>>b;
        Point p1 = {a, b};

        cout << contains(poly, p1) << endl;
    }
}


Measured memory_bytes: 3208
using static System.Console;
using static System.Convert;
class Program
{
    static void Main(string[] args)
    {
        var input = ReadLine().Split(' ');
        var num1 = ToInt32(input[0]);
        var dif = ToInt32(input[1]);
        var mod = ToInt32(input[2]);
        var result = "NO";
        for(var i = 1; i < num1*dif; i++)
        {
            if (i*num1 % dif == mod)
            {
                result = "YES";break;
            }
        }
        WriteLine(result);
    }
}



Measured memory_bytes: 11220
N = int(input())

def calc(n):
    ans = [0 for i in range(n+1)]
    for x in range(1,n+1):
        a = x**2
        if a>=n:
            break
        for y in range(1,1+n):
            b = y**2
            if b>=n:
                break
            for z in range(1,1+n):
                c = z**2
                if c>=n:
                    break
                f = a+b+c+x*y+y*z+z*x
                if f>n:
                    break
                ans[f]+=1
    return ans

res = calc(N)
for i in range(N):
    print(res[i+1])

Measured memory_bytes: 9236
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(10);
}
signed main(){
  init_io();
  ll n,m,id,jd,ans=0;
  cin >> n >> m;
  vector<ll> a(n),b(m),c(m),gre(n,0);
  vector<P> cb(m);
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  sort(a.begin(),a.end());
  for(int i=0;i<m;i++){
    cin >> b[i] >> c[i];
    cb[i] = P(c[i],b[i]);
  }
  sort(cb.begin(),cb.end(),greater<P>());
  id = 0;
  for(int i=0;i<n;){
    if(cb[id].second!=0){
      gre[i] = cb[id].first;
      i++;
      cb[id].second--;
    }else{
      id++;
      if(id == m) break;
    }
  }
  for(int i=0;i<n;i++){
    ans += max(a[i],gre[i]);
  }
  cout << ans << endl;
}


Measured memory_bytes: 4992
#include <iostream>
#include <string>

using namespace std;

int main(void) {
	int i;
	char c;
	string s;
	cin >> s;
	for (i = 0; i < s.size(); i++) {
		c = s[i];
		if (c == ',') {
			cout << " ";
		}
		else {
			cout << c;
		}
	}
	return 0;
}




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

int main() {
  int n;
  cin >> n;
  vector<int>data(n);
  for(int i = 0;i < n;i++) cin >> data[i];
  sort(data.begin(),data.end());
  if(data[n/2-1] == data[n/2]){
    cout << 0 << endl;
    return 0;
  }
  cout << data[n/2]-data[n/2-1] << endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <map>
using namespace std;
int main() {
    int N, M;
    string str;
    map<string, int>m;
    cin>>N;
    while (N--) {
        cin>>str;
        m[str]++;
    }
    cin>>M;
    while (M--) {
        cin>>str;
        m[str]--;
    }
    int ans = -200;
    for (map<string, int>::iterator it = m.begin(); it != m.end(); it++) {
        ans = max(ans, it->second);
    }
    if (ans < 0)
        ans = 0;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
//https://atcoder.jp/contests/keyence2019/tasks/keyence2019_c
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#ifdef BTK
#define DEBUG if(1)
#else
#define CIN_ONLY if(1)
struct cww {cww() {CIN_ONLY{ios::sync_with_stdio(false); cin.tie(0);}}}star;
#define DEBUG if(0)
#endif
#define ALL(v) (v).begin(),(v).end()
#define REC(ret, ...) std::function<ret (__VA_ARGS__)>
template <typename T>inline bool chmin(T &l, T r){bool a = l>r; if (a)l = r; return a;}
template <typename T>inline bool chmax(T &l, T r){bool a = l<r; if (a)l = r; return a;}
template <typename T>istream& operator>>(istream &is, vector<T> &v){for (auto &it : v)is >> it;return is;}
class range {private: struct I { int x; int operator*() { return x; }bool operator!=(I& lhs) { return x<lhs.x; }void operator++() { ++x; } }; I i, n;public:range(int n) :i({ 0 }), n({ n }) {}range(int i, int n) :i({ i }), n({ n }) {}I& begin() { return i; }I& end() { return n; }};


int main(){
    int N;
    cin>>N;
    vector<LL> ok,ng;
    vector<LL> A(N),B(N);
    cin>>A>>B;
    for(int i:range(N)){
        if(B[i]>A[i])ng.push_back(B[i]-A[i]);
        if(A[i]>B[i])ok.push_back(A[i]-B[i]);
    }
    int ret=0;
    LL need=0;
    for(auto &it:ng){
        need+=it;
        ret++;
    }
    sort(ALL(ok));
    reverse(ALL(ok));
    for(auto it:ok){
        if(need<=0){
            cout<<ret<<endl;
            return 0;
        }
        need-=it;
        ret++;
        if(need<=0){
            cout<<ret<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
    return 0;
}

Measured memory_bytes: 2936
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        Integer[] a = new Integer[n];
        Arrays.setAll(a, i -> Integer.parseInt(sc.next()));
        sc.close();

        // 主処理
        int target = 1;
        int count = 0;
        for (int i = 0; i < n; i++) {
            target = a[target - 1];
            count++;
            if (target == 2) {
                break;
            }
        }
        int result = target == 2 ? count : -1;

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 48456
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++)
        	arr[i] = sc.nextInt();
        int[] leftMax = new int[n];
        int max = 0;
        for(int i = 0; i < n; i++) {
        	leftMax[i] = max;
        	max = Math.max(max, arr[i]);
        }

        int[] rightMax = new int[n];
        max = 0;
        for(int i = n-1; i >= 0; i--) {
        	rightMax[i] = max;
        	max = Math.max(max, arr[i]);
        }
        for(int i = 0; i < n; i++)
        	System.out.println(Math.max(leftMax[i], rightMax[i]));
    }
}


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

P dp[100][100];
bool fi[100][100];

int main() {
  int h, w;
  cin >> h >> w;
  string s;
  rep(i, h) {
    cin >> s;
    rep(j, w) {
      if (s[j] == '.') fi[i][j] = 0;
      else fi[i][j] = 1;
    }
  }
//  rep(i, h) {rep(j, w) cout << fi[i][j]; cout << endl;}
  if (fi[0][0] == 1) {dp[0][0].first = 1; dp[0][0].second = 1;}
  else {dp[0][0].first = 0; dp[0][0].second = 0;}
  for (int i=1; i<w; i++) {
    if (fi[0][i-1] == fi[0][i]) {
      dp[0][i].first = dp[0][i-1].first; dp[0][i].second = dp[0][i-1].second;
    } else {
      dp[0][i].first = (dp[0][i-1].first + 1) % 2;
      dp[0][i].second = dp[0][i-1].second;
      if (dp[0][i].first == 1) dp[0][i].second++;
    }
  }
  for (int i=1; i<h; i++) {
    rep(j, w) {
      P d1, d2;
      if (j == 0) {
        if (fi[i][0] == fi[i-1][0]) {
          dp[i][0].first = dp[i-1][0].first;
          dp[i][0].second = dp[i-1][0].second;
        } else {
          dp[i][0].first = (dp[i-1][0].first + 1) % 2;
          dp[i][0].second = dp[i-1][0].second;
          if (dp[i][0].first == 1) dp[i][0].second++;
        }
      }

      else {if (fi[i][j-1] == fi[i][j]) {
        d1.first = dp[i][j-1].first;
        d1.second = dp[i][j-1].second;
      } else {
        d1.first = (dp[i][j-1].first + 1) % 2;
        d1.second = dp[i][j-1].second;
        if (d1.first == 1) d1.second++;
      }
      if (fi[i-1][j] == fi[i][j]) {
        d2.first = dp[i-1][j].first;
        d2.second = dp[i-1][j].second;
      } else {
        d2.first = (dp[i-1][j].first + 1) % 2;
        d2.second = dp[i-1][j].second;
        if (d2.first == 1) d2.second++;
      }
      if (d1.second > d2.second) {
        dp[i][j].first = d2.first; dp[i][j].second = d2.second;
      } else {
        dp[i][j].first = d1.first; dp[i][j].second = d1.second;
      }}
    }
  }
  cout << dp[h-1][w-1].second << endl;
}


Measured memory_bytes: 384
import math
from fractions import Fraction
from decimal import *
# ex) Fraction(2,6) > 1/3 > 0.33333

n = int(input())
x, y = map(int, input().split())
t, a = x, y

for _ in range(n - 1):
    tt, aa = map(int, input().split())

    # c = 1
    '''
    if (t >= a):
        c = math.ceil(tt / t)

    else:
        c = math.ceil(aa / a)
    '''
    # c = math.ceil(max(t / tt, a / aa))
    # c = math.ceil(max(Fraction(t + tt - 1, tt), Fraction(a + aa - 1 / aa)))
    c = max(math.ceil(Fraction(t, tt)), math.ceil(Fraction(a, aa)))
    c = max(1, c)

    t = tt * c
    a = aa * c


ans = t + a
print(ans)


Measured memory_bytes: 10480
INF = 10**18

def solve(N, Ma, Mb, sol):
    if N % 2 == 1:
        sol.append((0, 0, 0))
        N += 1

    M = N // 2

    sol1 = sol[:M]
    sol2 = sol[M:]

    S1 = []
    D = dict()
    res = INF

    for i in range(2**M):
        A1, B1, C1 = 0, 0, 0
        A2, B2, C2 = 0, 0, 0
        for j in range(M):
            if (i >> j) & 1:
                a1, b1, c1 = sol1[j]
                a2, b2, c2 = sol2[j]
                A1 += a1
                B1 += b1
                C1 += c1
                A2 += a2
                B2 += b2
                C2 += c2
        S1.append((A1, B1, C1))
        x = Mb * A2 - Ma * B2
        if x == 0 and C2 > 0:
            res = min(res, C2)
        if not x in D or 0 < C2 < D[x]:
            D[x] = C2

    for i in range(2**M):
        a, b, c = S1[i]
        x = Ma * b - Mb * a
        if x == 0 and c > 0:
            res = min(res, c)
        if x in D and D[x] + c > 0:
            res = min(res, D[x] + c)

    return res

N, Ma, Mb = map(int, input().split())
sol = [tuple(map(int, input().split())) for _ in range(N)]

res = solve(N, Ma, Mb, sol)

print(res if res != INF else -1)

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

int main() {
  int cell, s1, s2, s3;
  cin >> cell;
  s1 = cell/100;
  s2 = (cell-s1*100)/10;
  s3 = cell-s1*100-s2*10;
  cout << s1+s2+s3 << endl;

}


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

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> p(N);
  for (int i = 0; i < N; ++i) cin >> p[i];
  cout << accumulate(p.begin(), p.end(), 0) -
              *max_element(p.begin(), p.end()) / 2
       << endl;
  return 0;
}

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

int main () {
	
	long long int n=0, a=0, b=0;

	cin >> n >> a >> b;

	long long int dif = b-a;
	long long int res = 0;
	if (dif <= 1) cout << (n+1) << endl;
	else {

		//cout << "in" << endl;

		long long int m = n;
		res = 0;
		n = n - (a);


		//cout << "dif -> "<< dif <<  ", n - >" << n;

		if (n%2 == 0) res++;
		else n++;		
		n /= 2;
		res += n*b - ((n-1)*a);

		//cout << ", nn -> " << n << ", res -> "<< res << endl;

		res = max(m+1, res);

		cout << res << endl;
	}

	//cout << 58507834935779158 - 48518828981938099 << endl;

	return 0;
}

//314159265
//35897932
//384626433

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define mfill(x,y) memset(x,y,sizeof(x))
#define all(v) v.begin(), v.end()
#define in(x,y,h,w) if(0<=x&&x<h&&0<=y&&y<w)
#define y0 y12345
#define y1 y54321

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

using ul = unsigned long;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;using vvint = vector<vector<int>>;
using vll = vector<ll>;using vvll = vector<vector<ll>>;
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(a>b){a=b;return 1;}return 0;}
template <class T>void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}
template <class T>T gcd(T &a, T &b){if(a<b){swap(a,b);} T r = a%b; while(r!=0){a=b;b=r;r=a%b;} return b;}

vint dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
vint dx8 = {-1, -1, -1, 0, 1, 1, 1, 0}, dy8 = {-1, 0, 1, 1, 1, 0, -1, -1};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    debug("debug test\n");
    int n,m;cin>>n;
    if(n%2 == 0){
        cout << n << endl;
    }else{
        cout << n*2 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main () {
    int N;
    cin >> N;
    int list[N*3];
    for(int i = 0; i<N*3; i++) cin >> list[i];
    sort(list , list + N * 3 , greater<int>());
    long long res = 0;
    int teamcount = 0;
    for(int i = 0; i<N*3; i++) {
        if(i % 2 == 1 && teamcount < N) { 
            res += list[i];
            teamcount++;
        }
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <list>
using namespace std;

int main(){

    string s;
    cin >> s;

    int redcnt = 0;
    int bluecnt = 0;
    for(int i=0; i<s.length(); i++){
        if(s[i] == '0') redcnt++;
        else bluecnt++;
    }

    cout << min(redcnt, bluecnt)*2 << endl;

    return 0;
}

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

typedef long long ll;
using namespace std;

int N, Z, W;
int a[2010];
int ans;
int memo[2][2000][2000];

int solve(bool t, int k, int X) {
    if (memo[t][k][X] != -1)return memo[t][k][X];
    int res = abs(a[X] - a[N - 1]);

    for (int i = k + 1; i < N; i++) {
        if (t) {
            res = max(res, solve(!t, i, i - 1));
        } else {
            res = min(res, solve(!t, i, i - 1));
        }
    }
    return memo[t][k][X] = res;
}

int main() {
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2000; j++) {
            for (int k = 0; k < 2000; k++) {
                memo[i][j][k] = -1;
            }
        }
    }
    cin >> N >> Z >> W;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    ans = abs(a[N - 1] - W);
    for (int i = 1; i < N; i++) {
        ans = max(ans, solve(0, i, i - 1));
    }
    cout << ans << endl;
}

Measured memory_bytes: 31616
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
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; }
//V,P(大文字)使用不可

const ll INF=1000000000000000000;

signed main(){
    int n;
    cin>>n;
    V<int> x(n);
    cinf(n,x);
    int m;
    cin>>m;
    V<int> a(m);
    for(int i=0;i<m;i++){
        cin>>a[i];
        a[i]--;
    }
    V<bool> ok(2021,0);
    int t=0;
    for(int i=1;i<=2019;i++){
        if(i==x[t]){
            t++;
            ok[i]=1;
            if(t==n) break;
        }
    }
    for(int i=0;i<m;i++){
        if(x[a[i]]==2019||ok[x[a[i]]+1]) continue;
        ok[x[a[i]]]=0;
        x[a[i]]++;
        ok[x[a[i]]]=1;
    }
    for(int i=0;i<n;i++) cout<<x[i]<<endl;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
using P = pair<ll, ll>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep1(i, n) for(ll i=1;i<=(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define INF 1000000000

ll factorial(ll k) {
	ll sum = 1;
	for (ll i = 1; i <= k; ++i)
	{
		sum *= i;
	}
	return sum;
}

void solve_abc_146_a() {
	string S;
	ll ans = 0;

	cin >> S;

	if (S == "SUN") {
		ans = 7;
	}
	else if (S == "MON") {
		ans = 6;
	}
	else if (S == "TUE") {
		ans = 5;
	}
	else if (S == "WED") {
		ans = 4;
	}
	else if (S == "THU") {
		ans = 3;
	}
	else if (S == "FRI") {
		ans = 2;
	}
	else if (S == "SAT") {
		ans = 1;
	}

	cout << ans << "\n";
}

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

	solve_abc_146_a();

	return 0;
}

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

using namespace std;

int n, ans, a[100005];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort (a + 1, a + n + 1);
	int mark = 1;
	for (int i = 1; i < n; i++)
	{
		if (a[i] < 0) mark = i;
	}
	int now = a[mark];
	for (int i = 1; i < n; i++)
	{
		if (mark == i) continue;
		if (a[i] >= 0)
		{
			now -= a[i];
		}
	}
	ans = a[n];
	ans -= now;
	for (int i = 1; i < n; i++)
	{
		if (a[i] < 0 && i != mark)
		{
			ans -= a[i];
		}
	}
	cout << ans << endl;
	now = a[mark];
	for (int i = 1; i < n; i++)
	{
		if (mark == i) continue;
		if (a[i] >= 0)
		{
			cout << now << " " << a[i] << endl;
			now -= a[i];
		}
	}
	ans = a[n];
	cout << ans << " " << now << endl;
	ans -= now;
	for (int i = 1; i < n; i++)
	{
		if (a[i] < 0 && i != mark)
		{
			cout << ans << " " << a[i] << endl;
			ans -= a[i];
		}
	}
	return 0;
}

Measured memory_bytes: 2304
X, Y = gets.chomp.split(" ").map(&:to_i)
g1 = [1, 3, 5, 7, 8, 10, 12]
g2 = [4, 6, 9, 11]
g3 = [2]

result = (g1.include?(X) && g1.include?(Y) ||
          g2.include?(X) && g2.include?(Y) ||
          g3.include?(X) && g3.include?(Y) )

if result then puts "Yes" else puts "No" end

Measured memory_bytes: 1916
def solve(string):
    n, *ab = map(int, string.split())
    a, b = ab[:n + 1], ab[n + 1:]
    _sum = sum(a)
    for i, _b in enumerate(b[::-1]):
        diff = min(a[n - i], _b)
        _b -= diff
        a[n - i] -= diff
        a[n - i - 1] = max(0, a[n - i - 1] - _b)
    return str(_sum - sum(a))


if __name__ == '__main__':
    n = int(input())
    print(solve('{}\n'.format(n) + '\n'.join([input() for _ in range(2)])))


Measured memory_bytes: 28052
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	MyScanner sc = new MyScanner();
	Scanner sc2 = new Scanner(System.in);
	long start = System.currentTimeMillis();
	long fin = System.currentTimeMillis();
	final int MOD = 1000000007;
	int[] dx = { 1, 0, 0, -1 };
	int[] dy = { 0, 1, -1, 0 };

	void run() {
		System.out.println(sc.nextInt() * sc.nextInt());
	}

	public static void main(String[] args) {
		new Main().run();
	}

	void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	void debug2(char[][] array) {
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				System.out.print(array[i][j]);
			}
			System.out.println();
		}
	}

	boolean inner(int h, int w, int limH, int limW) {
		return 0 <= h && h < limH && 0 <= w && w < limW;
	}

	void swap(int[] x, int a, int b) {
		int tmp = x[a];
		x[a] = x[b];
		x[b] = tmp;
	}

	// find minimum i (a[i] >= border)
	int lower_bound(int a[], int border) {
		int l = -1;
		int r = a.length;
		while (r - l > 1) {
			int mid = (l + r) / 2;
			if (border <= a[mid]) {
				r = mid;
			} else {
				l = mid;
			}
		}
		// r = l + 1
		return r;
	}

	boolean palindrome(String s) {
		for (int i = 0; i < s.length() / 2; i++) {
			if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
				return false;
			}
		}
		return true;
	}

	class MyScanner {
		int nextInt() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-')
					return -nextInt();
				int res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		String next() {
			try {
				StringBuilder res = new StringBuilder("");
				int c = System.in.read();
				while (Character.isWhitespace(c))
					c = System.in.read();
				do {
					res.append((char) c);
				} while (!Character.isWhitespace(c = System.in.read()));
				return res.toString();
			} catch (Exception e) {
				return null;
			}
		}

		int[] nextIntArray(int n) {
			int[] in = new int[n];
			for (int i = 0; i < n; i++) {
				in[i] = nextInt();
			}
			return in;
		}

		int[][] nextInt2dArray(int n, int m) {
			int[][] in = new int[n][m];
			for (int i = 0; i < n; i++) {
				in[i] = nextIntArray(m);
			}
			return in;
		}

		double[] nextDoubleArray(int n) {
			double[] in = new double[n];
			for (int i = 0; i < n; i++) {
				in[i] = nextDouble();
			}
			return in;
		}

		long[] nextLongArray(int n) {
			long[] in = new long[n];
			for (int i = 0; i < n; i++) {
				in[i] = nextLong();
			}
			return in;
		}

		char[][] nextCharField(int n, int m) {
			char[][] in = new char[n][m];
			for (int i = 0; i < n; i++) {
				String s = sc.next();
				for (int j = 0; j < m; j++) {
					in[i][j] = s.charAt(j);
				}
			}
			return in;
		}
	}
}

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

int main(){
	int H,W;
  	cin >> H >> W;
  	vector<vector<char>> vec(H, vector<char>(W));
  	vector<bool> Hb(H, false);
  	vector<bool> Wb(W, false);
  	for(int i = 0; i < H;i++){
    	for(int j = 0; j < W;j++){
        	cin >> vec.at(i).at(j);
          	if(vec.at(i).at(j) == '#'){
            	Hb.at(i) = true;
              	Wb.at(j) = true;
            }
        }
    }
  	
  	for(int i = 0; i < H; i++){
    	if(Hb.at(i)){
        	for(int j = 0; j < W; j++){
            	if(Wb.at(j)){
                	cout << vec.at(i).at(j);
                }
            }
          cout << endl;
        }
    }
} 

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>

using namespace std;

bool P(int n) {
    return n % 2 == 0;
}

bool Q(int n) {
    return (n % 3 == 0) or (n % 5 == 0);
}

int main() {

    int N;
    cin >> N;

    bool ok = true;

    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;

        if (P(a)) {
            if (Q(a)) {

            } else {

                ok = false;
            }
        } else {
        }
    }

    if (ok) {
        cout << "APPROVED" << endl;
    } else {
        cout << "DENIED" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline

n = int(input())
a = [int(i) for i in input().split()]

def cond():
    for v in a:
        if v % 2 == 0 and (v % 3 != 0 and v % 5 != 0):
            return False
    return True

if cond():
    print('APPROVED')
else:
    print('DENIED')


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

int main() {
	int n, m, a;
	while (cin >> n >> m, n && m) {
		vector<int> p(n);
		for (int i = 0; i < m; ++i) {
			for (int& j : p) {
				cin >> a;
				j += a;
			}
		}
		cout << *max_element(p.begin(), p.end()) << endl;
	}
}


Measured memory_bytes: 3076
import numpy as np

H, W = (int(i) for i in input().split())

a = []
array = np.zeros((H,W))
for i in range(H):
    tmp = [i for i in input().split()]
    for j in range(W):
        if(tmp[0][j]=="."):
            array[i,j]=0
        else:
            array[i,j]=1

#---------------
survive_h = []
survive_w = []

for i in range(H):
    if(np.sum(array[i])!=0):
        survive_h.append(i)

for i in range(W):
    if(np.sum(array[:, i])!=0):
        survive_w.append(i)

deleted_array = array[survive_h][:,survive_w]

for i in range(len(deleted_array)):
    s=""
    for j in range(len(deleted_array[0])):
        if(deleted_array[i][j]==1):
            s += "#"
        else:
            s += "."
    print(s)


Measured memory_bytes: 12692
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long

int main(){
    ll n, a, b,add; 
    scanf("%lld %lld %lld",&n, &a, &b);
    add = n%(a+b) >a ?a:n%(a+b);
    printf("%lld", n/(a+b)*a+add);
    return 0;
}

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

int main() {
	int n,m;
	cin>>n>>m;
	vector<int>graph[n+1];
	vector<int>height(n+1);
	for(int i=1;i<=n;i++)
	cin>>height[i];
	for(int i=0;i<m;i++)
	{
	    int a,b;
	    cin>>a>>b;
	    graph[a].push_back(b);
	    graph[b].push_back(a);
	}
// 	for(int i=1;i<=n;i++)
// 	{
// 	    cout<<i<<"-->";
// 	    for(auto y:graph[i]) cout<<y<<" ";
// 	    cout<<"\n";
// 	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
	    int hi=height[i];
	    for(auto x:graph[i])
	    hi=max(hi,height[x]);
	    bool f=false;
	    if(hi==height[i])
	    {
	        for(auto y:graph[i])
	        if(hi==height[y]) f=true;
	        if(!f){
	            ans++;
	            //cout<<i<<" ";
	        } 
	    }
	}
//	cout<<"\n";
	cout<<ans;
	return 0;
}

Measured memory_bytes: 8816
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	io := NewIo()
	defer io.Flush()

	N := io.NextInt()
	M := io.NextInt()
	// fmt.Printf("%d %d %d\n", N, M, intMax(N, M))
	// fmt.Printf("Lucas %d %d\n", combMod(N, M, 13), combination(N, M))

	// write your own code here
	res := combination(N, 2) + combination(M, 2)
	fmt.Printf("%v\n", res)
}

// Libraries

type Io struct {
	reader    *bufio.Reader
	writer    *bufio.Writer
	tokens    []string
	nextToken int
}

func NewIo() *Io {
	return &Io{
		reader: bufio.NewReader(os.Stdin),
		writer: bufio.NewWriter(os.Stdout),
	}
}

func (io *Io) Flush() {
	err := io.writer.Flush()
	if err != nil {
		panic(err)
	}
}

func (io *Io) NextLine() string {
	var buffer []byte
	for {
		line, isPrefix, err := io.reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buffer = append(buffer, line...)
		if !isPrefix {
			break
		}
	}
	return string(buffer)
}

func (io *Io) Next() string {
	for io.nextToken >= len(io.tokens) {
		line := io.NextLine()
		io.tokens = strings.Fields(line)
		io.nextToken = 0
	}
	r := io.tokens[io.nextToken]
	io.nextToken++
	return r
}

func (io *Io) NextInt() int {
	i, err := strconv.Atoi(io.Next())
	if err != nil {
		panic(err)
	}
	return i
}

func (io *Io) NextFloat() float64 {
	i, err := strconv.ParseFloat(io.Next(), 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *Io) PrintLn(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}

func (io *Io) Printf(format string, a ...interface{}) {
	fmt.Fprintf(io.writer, format, a...)
}

func (io *Io) PrintIntLn(a []int) {
	b := []interface{}{}
	for _, x := range a {
		b = append(b, x)
	}
	io.PrintLn(b...)
}

func (io *Io) PrintStringLn(a []string) {
	b := []interface{}{}
	for _, x := range a {
		b = append(b, x)
	}
	io.PrintLn(b...)
}

func Log(name string, value interface{}) {
	fmt.Fprintf(os.Stderr, "%s=%+v\n", name, value)
}

func intMin(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func intMax(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// direct calculation of combination
// n, m should be "small"
func combination(n, m int) int {
	if m > n {
		return 0
	} else if m == n || m == 0 {
		return 1
	} else {
		res := 1
		for i := 0; i < m; i++ {
			res *= (n - i)
		}
		for i := 1; i <= m; i++ {
			res /= i
		}
		return res
	}
}

// caluclate combination modulo based on Lucas theorem
func lucas(n, m, p int) int {
	ntemp := n
	mtemp := m
	res := 1
	for i := 0; i < 100; i++ {
		// fmt.Printf("ntemp: %d\n", ntemp)
		nreminder := ntemp % p
		ntemp = ntemp / p
		mreminder := mtemp % p
		mtemp = mtemp / p
		res = res * (combination(nreminder, mreminder) % p)
		if ntemp == 0 {
			break
		}
	}
	return res % p
}

func combMod(n, m, p int) int {
	return lucas(n, m, p)
}


Measured memory_bytes: 640
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i=0;i<n;i++)a[i]=sc.nextInt();
        long money = 1000;
        long stock = 0;
        for (int i=0;i<n-1;i++){
            if (a[i]<a[i+1]){
                stock += money/a[i];
                money = money%a[i];
            }else {
                money +=stock*a[i];
                stock=0;
            }
        }
        money+=stock*a[n-1];
        System.out.println(money);
    }
}


Measured memory_bytes: 35852
# coding: utf-8
# Your code here!
from collections import deque
n,m = map(int,input().split())
g = {key:[] for key in range(n)}
for i in range(m):
    a,b = map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
#ans = {key:0 for key in range(1,n)}
d = deque([(0,g[0])])
C = {0:"Yes"}
#print(g)
while d != deque([]):
    #print(C,d)
    c = d.popleft()
    for i in c[1]:
        if i in C:
            continue
        else:
            d.append((i,g[i]))
            C[i] = c[0]+1
#print("Yes")
for i in range(n):
    if len(C) != n:
        print("No")
        break
    if i == 0:
        print("Yes")
    else:
        print(C[i])


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

using namespace std;

int main()
{
  //  ios_base::sync_with_stdio(false);
   // cin.tie(NULL);

    int n, d, x, answer = 0;
    cin >> n >> d >> x;

    for(int i = 1; i <= n; ++i)
    {
        int a, j = 1;
        cin >> a;

        while(j <= d)
        {
            ++answer;
            j += a;
        }

    }

    cout << answer + x << '\n';

}


Measured memory_bytes: 256
from collections import defaultdict

N, M = map(int, input().split())
H = [int(s) for s in input().split()]

edges = defaultdict(list)

for i in range(M):
    w = 1
    u, v = map(int, input().split())
    edges[u-1].append((v-1, w))
    edges[v-1].append((u-1, w))

# print(edges)

ans = 0
for i in range(N):
    c = True
    for v, w in edges[i]:
        if H[i] <= H[v]:
            c = False
            break
    ans += 1 if c else 0

print(ans)


Measured memory_bytes: 52308
def main():
	s = input()
	t = input()
 
	for i in reversed(range(len(s) - len(t) + 1)):
		if checker(s[i:(i + len(t))], t):
			s = s.replace("?", "a")
			print(s[:i] + t + s[i+len(t):])
			return
	print("UNRESTORABLE")
 
def checker(s, t):
	for i in range(len(s)):
		if s[i] != "?" and s[i] != t[i]:
			return False
	return True
 
if __name__ == '__main__':
	main()
 

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;
// vector<vector<int>> data(3, vector<int>(4));

void solve(long long N, vector<long long> a){
	ll amax = 0;
	rep(i, N) {
		amax = max(amax, a[i]);
	}
	ll res = 0;
	while(amax > N-1) {
		ll s = 0;
		rep(i, N) {
			s += a[i]/N;
		}
		res += s;
		rep(i, N) {
			a[i] = a[i]%N + (s - a[i]/N);
		}
		amax = 0;
		rep(i, N) {
			amax = max(amax, a[i]);
		}
	}
	cout << res << endl;
}

int main(){	
	long long N;
	scanf("%lld",&N);
	vector<long long> a(N-1+1);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&a[i]);
	}
	solve(N, a);
	return 0;
}



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

ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    ll r=a%b;
    while(r!=0){
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}

int main (){
   ll n,m;
   cin >> n >> m;
   cout << (1900*m+100*(n-m))*pow(2,m) <<endl; 
    return 0;
}


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


typedef long long ll;
const ll INF = 1000000000000000;


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

	vector<ll> P(N + 1), C(N + 1);
	for (int i = 1; i <= N; ++i) cin >> P[i];
	for (int i = 1; i <= N; ++i) cin >> C[i];

	ll ans = -INF;
	for (int s = 1; s <= N; ++s) {
		ll lp_tot = 0;
		ll lp_len = 0;
		int x = s;
		vector<bool> visited(N + 1, false);
		while (!visited[x]) {
			visited[x] = true;
			++lp_len;  lp_tot += C[x];
			x = P[x];
		}

		ll now = 0;
		for (int i = 1; i <= lp_len; ++i) {
			if (i > K) break;
			x = P[x]; now += C[x];
			ll sc = now;
			if (lp_tot > 0) sc += ((K - i) / lp_len) * lp_tot;
			ans = max(ans, sc);
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3276
# ACB054A
import sys
n, m = map(int, input().split())
N = []
M = []
for i in range(n):
    N.append(input())
for i in range(m):
    M.append(input())

for i in range(n-m+1):
    if M[0] not in N[i]:
        continue
    else:
        ind = N[i].index(M[0])
        A = True
        for j in range(m):
            if M[j] != N[i+j][ind:ind+m]:
                A = False
                break
        if A:
            print("Yes")
            sys.exit()
print("No")


Measured memory_bytes: 3064
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Main main = new Main();
		main.run();
	}

	public void run() {
		Scanner sc = new Scanner(System.in);
		int a=sc.nextInt();
		int b=sc.nextInt();
		int c=sc.nextInt();
		int d=sc.nextInt();
		int e=sc.nextInt();
		int f=sc.nextInt();

		long ans1 = 0;
		long ans2 = 100*a;
		double ans3 = 0;
		for(int i=0; 100*a*i<=f; i++) {
			for(int j=0; 100*b*j<=f; j++) {
				int w = 100*a*i+100*b*j;
				if(w==0) continue;
				if(w>f) continue;
				for(int k=0; c*k<=f; k++) {
					for(int l=0; d*l<=f; l++) {
						int s = c*k+d*l;
						if(s+w>f) continue;

						if(100.0*s/w>e) continue;
						double tmp = 100.0*s/(s+w);
						if(tmp>ans3) {
							ans1=s;
							ans2=w+s;
							ans3=tmp;
						}
					}
				}
			}
		}
		System.out.println(ans2+" "+ans1);
		sc.close();
	}

}


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

typedef long long lint;
typedef pair<int, int> P;
#define REP(i, x, n) for(int i = x ; i < n ; ++i)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; --i)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))

const int IINF = 1e9 + 10;
const lint LLINF = (lint)1e18 + 10;
const lint MOD = (lint)1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

int main(){
    int n, a, b;
    cin >> n >> a >> b;
    string s;
    cin >> s;
    int nai = 0, gai = 0;
    rep(i, s.size()){
        if(s[i] == 'c'){
            cout << "No" << endl;
        }else if(s[i] == 'a'){
            if(nai + gai < a + b){
                cout << "Yes" << endl;
                ++nai;
            }else{
                cout << "No" << endl;
            }
        }else{
            if(nai + gai < a + b && gai < b){
                cout << "Yes" << endl;
                ++gai;
            }else{
                cout << "No" << endl;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 896