akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
//#define inf 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define inv(x) Power(x, mod - 2)
#define fi first
#define se second
#define MP make_pair
#define PB push_back

using namespace std;
typedef pair<int,int> Pair;
typedef long double ld;
typedef long long ll;

const int mod = 998244353, MAX = 1e5, N = 50005;
//template{{{
const long double Pi = 3.14159265358979323846l;
inline int add(int x, int y) { x += y; return x >= mod ? x - mod : x; };
inline void inc(int &x, int y) { x += y; x -= (x >= mod ? mod : 0); }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline int Power(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = mul(ans, x);
		x = mul(x, x), y >>= 1;
	} return ans;
}

/*char buf[1<<23],obuf[1<<23],*p1=buf,*p2=buf, *O = obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
void print(int x) {
    if(x > 9) print(x / 10);
    *O++=x%10+'0';
} */

template <class T> inline T	input() {
	T x; char ch; bool flag = false;
	while (!isdigit(ch = getchar())) flag |= ch == '-';
	for (x = ch ^ 48; isdigit(ch = getchar()); x = x * 10 + (ch ^ 48));
	return flag ? -x : x;
}

template <class T> inline bool chkmin(T &x, T y) { x = x < y ? x : y; return x == y; }
template <class T> inline bool chkmax(T &x, T y) { x = x > y ? x : y; return x == y; }
template <class T> inline T gcd(T x, T y) { return !y ? x : gcd(y, x % y); }
template <class T> inline T sqrm(T x) { return (ll) x * x % mod; }
template <class T> inline T sqr(T x) { return x * x; }

struct {
	inline operator int () { return input<int>(); }
	inline operator long long () { return input<long long>(); }
	template <class T> inline void operator () (T &x) { x = *this; }
	template<class T, class ...A> inline void operator () (T &x, A &...a)
	{ x = *this; this -> operator ()(a...); }
} read; //}}}

long long A, B, n;

int main() {
#ifdef local
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
	freopen("log", "w", stderr);
#endif

	cin >> A >> B >> n;
	long long x = min(B - 1, n);
	cout << (A * x / B) - A * (x / B) << endl;
	return 0;
}


Measured memory_bytes: 3588
import sys, bisect
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def lis(a):
    dp = [INF]*len(a)
    for i in a:
        idx = bisect.bisect_left(dp, i)
        dp[idx] = i
    return bisect.bisect_left(dp, INF)

def resolve():
    n = I()
    a = [I() for _ in range(n)]

    print(lis(a))

if __name__ == '__main__':
    resolve()



Measured memory_bytes: 10476
#include <iostream>

using namespace std;

bool m[26];

int main() {
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); ++i) m[s[i] - 'a'] = true;
  for (int i = 0; i < 26; ++i) {
    if (!m[i]) {
      cout << char(i + 'a') << endl;
      return 0;
    }
  }
  puts("None");
}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main(){
    int n,x;cin>>n>>x;
    if(x==1||2*n-1==x){
        cout<<"No"<<endl;
    }
    else{
        cout<<"Yes"<<endl;
        int t=x-n;
        if(t>=0){
            for(int i=1+t;i<=2*n-1;i++){
                cout<<i<<endl;
            }
            for(int i=1;i<=t;i++){
                cout<<i<<endl;
            }
        }else {
            t*=-1;
            for(int i=t;i>=1;i--){
                cout<<2*n-i<<endl;
            }
            for(int i=1;i<=2*n-1-t;i++){
                cout<<i<<endl;
            }
        }
    }
return 0;
}


Measured memory_bytes: 1536
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

//a,b,c
//a,c,b
//c,a,b
//b,a,c
//c,b,a
//b,c,a

int main() {
  int a,b,c;
  cin >> a >> b >> c;
  if(a < b){
    if(b < c){
      cout << a << " " << b << " " << c << endl;
    }else if(a < c){
      cout << a << " " << c << " " << b << endl;
    }else{
      cout << c << " " << a << " " << b << endl;
    }
  }else{
    if(a < c){
      cout << b << " " << a << " " << c << endl;
    }else if(c < b){
      cout << c << " " << b << " " << a << endl;
    }else{
      cout << b << " " << c << " " << a << endl;
    }
  }
    return 0;
}



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

using namespace std;

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

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

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

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


signed main(void) {
    string s;
    cin >> s;
    rep(i,s.size()){
        if(i%2){
            if(s[i] == 'L' || s[i] == 'U' || s[i] == 'D')continue;
        }else{
            if(s[i] == 'R' || s[i] == 'U' || s[i] == 'D')continue;
        }
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 256
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Code author: Saurabh Singhal
Code copy karne vaale tera muh kaala
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/

#include<bits/stdc++.h>
#define mp(a,b) make_pair(a,b)
#define pb push_back
#define ppb pop_back

using namespace std;
typedef long long int ll;
typedef vector<int> vi_t;
typedef vector<ll> vll_t;
int t=1;
vll_t a,b;
bool is(string s1, string s2){
    int m = s1.length(); 
    int n = s2.length(); 
    for (int i=0;i<=n-m;i++) { 
        int j=0;
        for (j=0;j<m;j++){
            if (s2[i+j]!=s1[j]){
                break; 
            }
        }
  		if(j==m){ 
            return true;
        } 
    } 
    return false; 
}
int  main(){
	// #ifndef ONLINE_JUDGE
 //    // for getting input from input.txt
 //    freopen("input.txt", "r", stdin);
 //    // for writing output to output.txt
 //    freopen("output.txt", "w", stdout);
	// #endif
	string s,t;
	cin>>s>>t;
	s+=s;
	if(is(t,s)){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
}

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

int h, w, k;
char s[310][310];
int a[310][310];
vector<int> v;

int main() {
	scanf("%d%d%d", &h, &w, &k);
	for (int i = 1; i <= h; ++i)
		scanf("%s", s[i] + 1);
	int cnt = 0;
	int r = 0;
	bool ok = false;
	for (int i = 1; i <= h; ++i) {
		bool flag = false;
		int p;
		for (int j = 1; j <= w; ++j) {
			if (s[i][j] == '#') {
				flag = true;
				p = j;
				break;
			}
		}
		if (!flag) {
			if (ok) v.push_back(i);
			continue;
		}
		if (!ok) r = i - 1;
		ok = true;
		++cnt;
		for (int j = 1; j <= w; ++j) {
			if (s[i][j] == '#' && j != p)
				++cnt;
			a[i][j] = cnt;
		}
	}
	
	for (int i = r; i >= 1; --i) {
		for (int j = 1; j <= w; ++j) {
			a[i][j] = a[i + 1][j];
		}
	}
	for (int i = 0; i < v.size(); ++i) {
		for (int j = 1; j <= w; ++j) {
			a[v[i]][j] = a[v[i] - 1][j];
		}
	}
	
	for (int i = 1; i <= h; ++i) {
		for (int j = 1; j <= w; ++j) {
			printf("%d ", a[i][j]);
		}
		printf("\n");
	}
	
	return 0;
	
}

Measured memory_bytes: 1280
#!/usr/bin/env python

n = int(input())
s = [input() for _ in range(n)]

d = {}
for i in range(len(s[0])):
    if s[0][i] not in d:
        d[s[0][i]] = 1 
    else:
        d[s[0][i]] += 1

for i in range(n):
    for key in d.keys():
        tmp = 0 
        for k in range(len(s[i])):
            if s[i][k] == key:
                tmp += 1
        if tmp <= d[key]:
            d[key] = tmp 

# print('d =', d)
d = sorted(d.items(), key=lambda x:x[0])
ans = ''
for i in range(len(d)):
    for _ in range(d[i][1]):
        ans += d[i][0]
print(ans)


Measured memory_bytes: 9136
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define fi first
#define se second
#define pb push_back
#define forn(i,n) for(int i=0;i<(n);i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define forr(i,n) for(int i=n;i>=0;i--)
#define all(x) x.begin(), x.end()
const int MAXN =  305;

void fio(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}

int C[MAXN][MAXN], sum[MAXN][MAXN], dp[MAXN][MAXN];

int main(){
  fio();
  int N,K,M; cin>>N>>K>>M;
  N++;
  for(int i=0;i<=N;i++)
    for(int j=0;j<=i;j++)
      C[i][j] = j>0?(C[i-1][j-1] + C[i-1][j])%M : 1;
  forn(i,K+1) dp[1][i]=1;
  for(int i = K;~i;i--)
    sum[1][i]= (sum[1][i+1] + dp[1][i])%M;
  for(int n=2;n<=N;n++){
    for(int x=0;x<=K;x++)
      for(int k=1; k<n;k++)
        dp[n][x] = (dp[n][x] + (LL)sum[k][x+1]*C[n-2][k-1]%M*dp[n-k][x])%M;
    for(int i = K;i>=0;--i)
       sum[n][i] = (sum[n][i+1] + dp[n][i])%M;
  }
  cout<<dp[N][0]<<endl;
    return 0;
}



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

typedef long long LL;

int main()
{
    //freopen("./test.txt","r",stdin);

    LL A,B,C;
    scanf("%lld %lld %lld",&A,&B,&C);

    if(A % 2 == 0 || B % 2 == 0 || C % 2 == 0)
    {
        puts("0");
    }
    else
    {
        LL res = min(A*B,min(B*C,A*C));
        printf("%lld\n",res);
    }

    return 0;

}



Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int main() {
    vector<int> fibs(45);
    fibs[0] = fibs[1] = 1;
    for (int i = 2; i <= 44; i++) {
        fibs[i] = fibs[i - 1] + fibs[i - 2];
    }
    int n;
    cin >> n;
    cout << fibs[n] << endl;
}

Measured memory_bytes: 1196
n,m=map(int,input().split())
lr=[list(map(int,input().split())) for l in range(m)]
min=1000000
max=0
for i in range(m):
    if lr[i][1]<min:
        min=lr[i][1]
    if lr[i][0]>max:
        max=lr[i][0]
if (min-max)>=0:
    print((min-max)+1)
else:
    print(0)

Measured memory_bytes: 27336
#include <functional>
#include <list>
#include <string>
#include <vector>
#include <climits>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <set>
#include <deque>
#include <stack>
#include <cassert>
using namespace std;
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define ALL(x) (x).begin(),(x).end()
#define CASET2 int ___T, case_n = 1; scanf("%d ", &___T); while ((___T > 0 ? printf("Case #%d:\n", case_n++) : 0), ___T-- > 0)
#define CASET1 int ___T, case_n = 1; scanf("%d ", &___T); while ((___T > 0 ? printf("Case #%d: ", case_n++) : 0), ___T-- > 0)
#define CASET int ___T; scanf("%d ", &___T); while (___T-- > 0)
#define SZ(X) ((int)(X).size())
#define LEN(X) strlen(X)
#define REP(i,n) for(int i=0;i<int(n);i++)
#define REP1(i,a,b) for(int i=(a);i<=int(b);i++)
#define PER1(i,a,b) for(int i=(a);i>=(b);i--)
#define REPL(i,x) for(int i=0;x[i];i++)
#define PER(i,n) for(int i=(n)-1;i>=0;i--)
#define RI1(x) scanf("%d",&x)
#define RI2(x,y) RI1(x), RI1(y)
#define RI3(x,y...) RI1(x), RI2(y)
#define RI4(x,y...) RI1(x), RI3(y)
#define RI5(x,y...) RI1(x), RI4(y)
#define RI6(x,y...) RI1(x), RI5(y)
#define GET_MACRO(_1, _2, _3, _4, _5, _6, NAME, ...) NAME
#define RI(argv...) GET_MACRO(argv, RI6, RI5, RI4, RI3, RI2, RI1)(argv)
#define DRI(argv...) int argv;RI(argv)
#define WRI(argv...) while (RI(argv) != EOF)
#define DWRI(x...) int x; WRI(x)
#define RS(x) scanf("%s",x)
#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 X first
#define Y second
#define V(x) vector<x >

typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long LL;
const int INF = 1000000000;

void print(int i) { printf("%d", i); }
template<class T> void PI(T i) { print(i); puts(""); }
template<class T> void PIS(T i) { print(i); printf(" "); }

template<class T>
void PV(T const &v, int N) {
    REP(i, N) {
        print(v[i]);
        printf("%c", i == N-1 ? '\n' : ' ');
    }
}

template<class T> void PV(T const &v) { PV(v, SZ(v)); }

template<class T, class S> bool has_bit(T mask, S i) { return (mask >> i) & 1; }
long long shift(int i) { return 1ll << i; }

template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
int popcount(int x) { return __builtin_popcount(x); } 
int popcount(long long x) { return __builtin_popcountll(x); } 

#include <unordered_set>
#include <unordered_map>
#define EB emplace_back
#define RL(x) scanf("%lld", &(x))
#define PL(x) printf("%lld\n", x)
#define DRL(x) LL x; RL(x)

int main() {
  DRI(N);
  int p[N+1], inv[N+1], a[N+1], b[N+1];
  REP1(i, 1, N) {
    RI(p[i]);
    inv[p[i]] = i;
  }
  a[1] = 1; b[1] = INF;
  REP1(i, 2, N) {
    a[i] = a[i-1] + 1;
    b[i] = b[i-1] - 1;
    if (inv[i] > inv[i-1]) {
      a[i] += inv[i] - inv[i-1];
    } else {
      b[i] -= inv[i-1] - inv[i];
    }
  }
  PV(a+1, N);
  PV(b+1, N);

  return 0;
}


Measured memory_bytes: 896
////////////////////////////////////////////
///                                      ///
///         Template ver. 1 rapel        ///
/// Fear is Temporary, Regret is Forever ///
///          Must Try and Get AC         ///
///                                      ///
////////////////////////////////////////////
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <iomanip>

#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <utility>

#include <math.h>
#include <complex>

#include <assert.h>
#include <time.h>
//#include <chrono>
//#include <random>

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <bitset>

#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define endl '\n'
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

void desperate_optimization(int precision){
  	ios_base::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	cout.setf(ios::fixed);
  	cout.setf(ios::showpoint);
  	cout.precision(precision);
}

const int N = 2e5;
int A[N + 5], B[N + 5];
LL tot = 0;

void hora(int tc) {
	int n;
	cin>>n;
	for(int i = 0;i < n;i++) cin>>A[i];
	for(int i = 0;i < n;i++) cin>>B[i];
	queue<int> q;
	for(int i = 0;i < n;i++) {
		if(B[i] > B[(i + 1) % n] + B[(i + n - 1) % n]) q.push(i);
	}
	while(!q.empty()) {
		int i = q.front();
		q.pop();
		if(B[i] <= B[(i + 1) % n] + B[(i + n - 1) % n]) continue;
		int bawah = A[i];
		int diff = B[i] - bawah;
		int ctr = diff / (B[(i + 1) % n] + B[(i + n - 1) % n]);
		tot += ctr;
		B[i] -= ctr * (B[(i + 1) % n] + B[(i + n - 1) % n]);
		if(B[(i + 1) % n] > B[i] + B[(i + 2) % n]) q.push((i + 1) % n);
		if(B[(i + n - 1) % n] > B[i] + B[(i + n - 2) % n]) q.push((i + n - 1) % n);
//		for(int i = 0;i < n;i++) cout<<B[i]<<" ";
//		cout<<endl;
	}
	for(int i = 0;i < n;i++) if(A[i] != B[i]) tot = -1;
	cout<<tot<<endl;
}

int main(){
	desperate_optimization(10);
	int ntc = 1;
	//cin>>ntc;
	for(int tc = 1;tc <= ntc;tc++) hora(tc);
	return 0;
}




Measured memory_bytes: 2176
# -*- coding: utf-8 -*-
"""
Contents   : AtCoder Regular Contest 94 C問題 
Author     : Kitaura Hiromi
LastUpdate : 20180414
Since      : 20180414
https://img.atcoder.jp/arc094/editorial.pdf
"""

A, B, C = map(int, input().split(" "))
cnt = 0

if (A%2 == B%2) and (B%2 == C%2):
    pass
else:
    if A%2 == B%2:
        A += 1
        B += 1
        cnt += 1
    elif A%2 == C%2:
        A += 1
        C += 1
        cnt += 1
    else:
        B += 1
        C += 1
        cnt += 1

ABC = sorted([A, B, C])
cnt += (ABC[2] - ABC[1]) // 2
cnt += (ABC[2] - ABC[0]) // 2
print(cnt)

Measured memory_bytes: 3064
# -*- coding: utf-8 -*-
s = list(map(int,list(input())))
k = int(input())

flag = 0

for i in range(len(s)):
    if flag == 0 and s[i] == 1:
        s[i] = 1
    elif flag == 0:
        s[i] = s[i]
        flag = s[i]
    else:
        s[i] = flag

if k > len(s):
    print(s[-1])
else:
    print(s[k-1])


Measured memory_bytes: 3064
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks))
        chosen = set([pick] if maks <= 0 else [i for i in indexes if c[i] > 0])
        is_chosen = [(i in chosen) for i in range(n)]

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        if len(c) > 1 and not is_chosen[0]:
            res += [0]
            del c[0], is_chosen[0]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()


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

int main() {
  int n, m;
  cin >> n >> m;
  vector<string> a(n), b(m);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < m; i++) {
    cin >> b[i];
  }

  bool include = false;
  for (int s = 0; s < n-m+1; s++) {
    for (int t = 0; t < n-m+1; t++) {
      bool flag = true;
      for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
          if (a[s+i][t+j] != b[i][j]) {
            flag = false;
          }
        }
      }
      if (flag) include = true;
    }
  }

  cout << (include ? "Yes" : "No");
}

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

ll solve() {
    int n;
    cin >> n;
    vector<ll> A(n);
    rep(i,n) cin >> A[i];
    ll X = 0;
    for (int i = 2; i < n; i++) {
        X ^= A[i];
    }
    if (A[0]+A[1] < X) return -1;
    // a+b = A[0]+A[1]
    // a^b = X
    // a+b = a^b + (a&b)*2
    // a&b = ((a+b) - (a^b))/2
    ll D = (A[0]+A[1] - X)/2;
    if (A[0] < D) return -1;
    ll a = D;
    for (int k = 60; k >= 0; k--) {
        if (((a|bit(k)) <= A[0]) && (bit(k)&X)) {
            a |= bit(k);
        }
    }
    if (a == 0) return -1;
    ll b = (A[0]-a+A[1]);
    if ((a&b) != D) return -1;
    return A[0]-a;
}

int main(void){
    cout << solve() << endl;
    return 0;
}


Measured memory_bytes: 3628
W,H,N=map(int,input().split())
MAP=[[0 for i in range(W)] for j in range(H)]
command=[list(map(int,input().split())) for i in range(N)]
for x,y,a in command:
    if a==1:
        for i in range(H):
            for j in range(x):MAP[i][j]=1
    elif a==2:
        for i in range(H):
            for j in range(x,W):MAP[i][j]=1
    elif a==3:
        for i in range(y):
            for j in range(W):MAP[i][j]=1
    else:
        for i in range(y,H):
            for j in range(W):MAP[i][j]=1
cnt=0
for i in range(H):
    cnt +=MAP[i].count(0)
print(cnt)

Measured memory_bytes: 3188
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
B = np.array(lr() + [10 ** 6])
answer = B[0] + np.minimum(B[:-1], B[1:]).sum()
print(answer)


Measured memory_bytes: 12384
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n,l,t;
  cin>>n>>l>>t;
  l*=2;
  t*=2;
  vector<Int> xs(n),ws(n);
  for(Int i=0;i<n;i++) cin>>xs[i]>>ws[i],xs[i]*=2;

  vector<Int> pos(n);
  for(Int i=0;i<n;i++){
    pos[i]=xs[i]+(ws[i]==1?1:l-1)*t;
    pos[i]%=l;
  }

  Int idx=-1;
  for(Int i=0;i<n;i++){
    if(ws[i]!=1) continue;
    idx=i;
    break;
  }

  if(idx<0){
    for(Int i=0;i<n;i++) cout<<pos[i]/2<<endl;
    return 0;
  }

  Int cur=idx;
  for(Int i=0;i<n;i++){
    if(ws[i]==1) continue;
    Int s=0;
    if(i<idx) s=(l-(xs[idx]-xs[i]))/2;
    else s=(xs[i]-xs[idx])/2;
    if(s>t) continue;
    cur+=1;
    cur+=(t-s)/(l/2);
    cur%=n;
  }
  // cout<<idx<<" "<<cur<<endl;

  vector<Int> qs;
  for(Int i=0;i<n;i++){
    qs.emplace_back(pos[i]);
    qs.emplace_back(pos[i]+l);
  }
  sort(qs.begin(),qs.end());

  vector<Int> ans(n);
  for(Int i=0;i<n;i++){
    if(qs[i]!=pos[idx]) continue;
    if(qs[i]==qs[i+1]) continue;

    for(Int j=0;j<n;j++)
      ans[(cur+j)%n]=qs[i+j]%l;
    break;
  }
  for(Int i=0;i<n;i++) cout<<ans[i]/2<<endl;
  return 0;
}


Measured memory_bytes: 5872
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> adj[200005];
bool vis[200005];

vector<int> bfs(int u){
	queue<int>q;
	q.push(u);
	memset(vis, false, sizeof(vis));
	vector<int> level(200005);
	while(!q.empty()){
		int x = q.front();
		vis[x] = true;
		q.pop();
		for(auto nei : adj[x]){
			if(!vis[nei]){
				q.push(nei);
				level[nei] = level[x] + 1; 
			}
		}
	}
	return level;
}

signed main(){
	int n, u, v, x, y;
	cin>>n>>u>>v;
	for(int i=0; i<n-1; i++){
		cin>>x>>y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	int ans = -1;
	vector<int> aoki = bfs(v);
	vector<int> tash = bfs(u);
	for(int i=1; i<=n; i++){
		if(aoki[i] > tash[i])
			ans = max(aoki[i]-1, ans);
	}
	cout<<ans;
}

Measured memory_bytes: 12160
def main():
  N = int(input())
  A = list(map(int,input().split()))
  B = list(map(int,input().split()))
  # M:カードの数字の最大値+1
  M = max(max(A),max(B))+1
  INF=float('inf')
  # dp[mask][a]:maskのカードが操作済で、そのうち右端のカードの数字がaであるときの操作回数の最小値
  dp = [[INF for _ in range(M)] for _ in range(1<<N)]
  dp[0][0] = 0
  
  for i in range(1<<N):
    # idx:操作済カードの枚数
    idx = 0
    for k in range(N):
      #k番目のカードが操作済みかどうか判定する。iでk番目にフラグがたってたら、操作済みとする。
      if (i>>k)&1 == 1:
        idx += 1
    for j in range(M):
      if dp[i][j] >= INF:
        continue
      for k in range(N):
        # k:右端の操作済カードの次に来るカード
        # kがすでに操作済の場合はcontinueする
        if (i>>k)&1:
          continue
        
        # kが何回操作されるかによってkの数字が表の数字になるか裏の数字になるかが決まる
        if abs(k-idx)%2 == 0:
          c = A[k]
        else:
          c = B[k]
  
        # kの数字広義単調増加にならない場合はcontinue
        if j > c:
          continue
        
        # t:kを右端の操作済カードの次に並べるための操作回数
        # それは、初期配置でkより左にあってまだ操作済でないカードの枚数と一致する
        t = 0
        for l in range(k):
          if (i>>l)&1 == 0:
            t += 1
        #print(i,k,idx,c,dp[i|(1<<k)][c],t)
        dp[i|(1<<k)][c] = min(dp[i|(1<<k)][c],dp[i][j]+t)
  
  ans = INF
  for i in range(M):
    ans = min(dp[(1<<N)-1][i],ans)
  print(ans if ans < INF else -1)

if __name__ == '__main__':
  main()

Measured memory_bytes: 419904
n,k,q = map(int,input().split())
li = []
score = []
count = []

for i in range(q):
    a = int(input())
    li.append(a)

for i in range(n):
    score.append(k)
    count.append(0)

for i in range(q):
    count[li[i]-1]+=1

for i in range(len(score)):
    score[i] = score[i] - q + count[i]
for i in range(len(score)):
    if score[i]>0:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 12564
#include <bits/stdc++.h>
    using namespace std;
     
    int main(){
      long long N, K;
      cin >> N >> K;
      vector<pair<long long, long long>> td(N);
      for (int i=0; i<N; i++) {
        cin >> td[i].first >> td[i].second;
        td[i].first--;
      }
      long long ans = 0;
      vector<long long> vari(N,0);
      sort(td.begin(), td.end(), [](const auto& a, const auto& b){return a.second>b.second;});
      priority_queue<long long, vector<long long>, greater<long long> > pque;
      long long vnum = 0;
      for (int i=0; i<K; i++){
        if (vari[td[i].first]==0){
          vari[td[i].first]++;
          ans += vnum*2 + 1;
          vnum++;
          ans += td[i].second;
        }
        else {
          ans += td[i].second;
          pque.push(td[i].second);
        }
      }
      long long fans = ans;
      for (int i=K; i<N; i++){
        if (pque.empty()) break;
        if (vari[td[i].first]>0) continue;
        vari[td[i].first]++;
        ans -= pque.top();
        pque.pop();
        ans += vnum*2 + 1;
        ans += td[i].second;
        vnum++;
        fans = max(ans, fans);
      }
      cout << fans << endl;
    }

Measured memory_bytes: 3196
#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)
#define out(ans) cout << ans << endl;
const long long mod = 1e9 + 7;

int main(){

  int n;cin>>n;
  if(n<1000){out("ABC");}
  else out("ABD");


  return 0;
}


Measured memory_bytes: 256
H,W = list(map(int,input().split()))
A = []
for i in range(H):
    A.append(list(map(int,input().split())))

cnt = 0
ope = []
for i in range(H):
    nowH = i
    for j in range(W):
        if i%2==1:
            nowW = W-1-j
        else:
            nowW = j

        if j==W-1:
            nextH = i+1
            nextW = nowW
        else:
            nextH = nowH
            if i%2==1:
                nextW = nowW-1
            if i%2==0:
                nextW = nowW+1

        if nextH>=H or nextW>=W:
            break

        if A[nowH][nowW]%2==1:
            A[nowH][nowW] += -1
            A[nextH][nextW] += 1
            ope.append([nowH+1,nowW+1,nextH+1,nextW+1])
            cnt+=1

print(cnt)
for i in range(len(ope)):
    print(ope[i][0],ope[i][1],ope[i][2],ope[i][3])


Measured memory_bytes: 72028
#include <bits/stdc++.h>
using namespace std;
int main()
{
int x,a,b,c;
cin>>a>>b>>c>>x;
int ans=0;
for(int i=0;i<=a;i++)
{
    for(int j=0;j<=b;j++)
    {
        int s=i*500+j*100;
        if(s>x)
        continue;
        if((x-s)%50==0&&((x-s)/50<=c))
        ans++;
    }
}
cout<<ans;
return 0;
}
 


Measured memory_bytes: 256
using System.Collections.Generic;
using System.IO;
using System.Linq;
using static System.Console;
class Z { static void Main() => new K(); }
class K
{
	int[] G => ReadLine().Split().Select(int.Parse).ToArray();
	public K()
	{
		SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
		Solve();
		Out.Flush();
	}
	int V, Mod;
	List<int>[] es;
	void Solve()
	{
		var I = G;
		V = I[0];
		Mod = I[1];
		es = new List<int>[V];
		for (var u = 0; u < V; u++) es[u] = new List<int>();
		for (var e = 0; e < V - 1; e++)
		{
			I = G;
			es[I[0] - 1].Add(I[1] - 1);
			es[I[1] - 1].Add(I[0] - 1);
		}
		var dp0 = DFS0(0, V);
		var dp1 = DFS1(0, dp0);
		for (var u = 0; u < V; u++) WriteLine(dp0[u] * (dp1[u] + 1) % Mod);
	}
	long[] DFS0(int u, int p)
	{
		var dp0 = new long[V];
		var st = new Stack<A0>();
		st.Push(new A0(u, p));
		while (st.Count > 0)
		{
			var f = st.Pop();
			if (f.p >= 0)
			{
				es[f.u].Remove(f.p);
				st.Push(new A0(f.u, -1));
				foreach (var v in es[f.u]) st.Push(new A0(v, f.u));
			}
			else
			{
				dp0[f.u] = 1L;
				foreach (var v in es[f.u]) dp0[f.u] = dp0[f.u] * (dp0[v] + 1) % Mod;
			}
		}
		return dp0;
	}
	long[] DFS1(int u, long[] dp0)
	{
		var dp1 = new long[V];
		var st = new Stack<int>();
		st.Push(u);
		var x = new long[V + 1];
		var y = new long[V + 1];
		while (st.Count > 0)
		{
			u = st.Pop();
			var W = es[u].Count;
			x[0] = y[W] = 1;
			for (var i = 0; i < W; i++) x[i + 1] = x[i] * (dp0[es[u][i]] + 1) % Mod;
			for (var i = W - 1; i >= 0; i--) y[i] = y[i + 1] * (dp0[es[u][i]] + 1) % Mod;
			for (var i = 0; i < W; i++) dp1[es[u][i]] = (dp1[u] + 1) * x[i] % Mod * y[i + 1] % Mod;
			foreach (var v in es[u]) st.Push(v);
		}
		return dp1;
	}
}
struct A0 { public int u, p; public A0(int u, int p) { this.u = u; this.p = p; } }


Measured memory_bytes: 36092
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <string>
#include <utility>
#include <map>
int main() {
    int X, Y;
    std::cin >> X >> Y;
    int res = 1; for(int i = 0; i < X; i++) res *= 100;
    if(Y<= 99){
        std::cout << Y * res;
    }else if(Y==100){
        std::cout << 101 * res;
    }
    return 0;
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define MOD 1000000007
#define el endl
#define INF 1e8
typedef long long ll;
typedef long double ld;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    
    vector<ll> s(n+1);
    for(int i = 1; i < n+1; i++){
        s[i] = s[i-1] + a[i-1];
    }
    ll ans = 0;
    ll cnt = 1;
    sort(s.begin(), s.end());
    for(int i = 0; i < s.size()-1; i++){
        if(s[i] == s[i+1]){
            cnt++;
        }else{
            ans += (cnt * (cnt-1)) / 2;
            cnt = 1;
        }
    }
    ans += (cnt * (cnt-1)) / 2;
    cout << ans << endl;
}



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

bool isPrime(ll n){
    if(n >= 2){
        for(int i = 2; i * i <= n; ++i){
            if(n % i == 0) return false;
        }
        return true;
    }
    return false;
}

int main() {
    ll X;
    cin >> X;

    while(!isPrime(X)) ++X;

    cout << X << endl;
}

Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const double PI2 = 8.0 * atan(1.0);
 
#define REP(i,n)	for(int i=0;i<(int)n;++i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define FOR(i,s,n)	for(int i=s;i<(int)n;++i)

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    ll cnt = 0;
    for(int i=0;i<n;i++) {
        if(a[i]%2==1)
            cnt++;
    }
    if(cnt%2==1)
        cout << "NO" << endl;
    else
        cout << "YES" << endl;

}


Measured memory_bytes: 1024
/**
 * Title: A - Frog 1
 * Url: https://atcoder.jp/contests/dp/tasks/dp_a
 */
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int MAX_N = 100000;

int main() {
    int n; cin >> n;
    int h[MAX_N+1];
    int cost[MAX_N+1];
    for(int i=0; i<n; i++) cin >> h[i+1];
    for(int i=1; i<=n; i++) {
        if(i==1) {
            cost[i] = 0;
        } else if(i==2) {
            cost[i] = abs(h[2]-h[1]);
        } else {
            cost[i] = min(cost[i-1]+abs(h[i]-h[i-1]), cost[i-2]+abs(h[i]-h[i-2]));
        }
    }

    cout << cost[n] << endl;


    return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cstring>

const int maxn=3000+5;

int vis[maxn][maxn];

double d[maxn][maxn]; // 递推 现在在第j个,需要k个朝上的概率 

double p[maxn];

double dp(int,int);

int main(){
	
	int n; scanf("%d",&n);

	for(int i = 1; i <= n; i++){
	
		scanf("%lf",&p[i]);
	}

	double ans = 0;

	int middle = n / 2;

	memset(vis,-1,sizeof(vis));

	d[0][0] = 1.0; vis[0][0] = 1;

	for(int i = middle+1; i <= n; i++){
	
		ans += dp(n,i);
	}

	printf("%.10lf\n",ans);

	return 0;
}	

double dp(int n,int m){
	
	/*printf("%d %d\n",n,m);*/
	
	if(vis[n][m] != -1) return d[n][m];

	else {
		
		vis[n][m] = 1;

		d[n][m] = 0;

		if(m) d[n][m] += p[n] * dp (n - 1,m - 1);

		if(n>m) d[n][m] += (1 - p[n]) * dp(n - 1,m);

		/*printf("%d %d : %.3lf\n",n,m,d[n][m]);*/

		return d[n][m];

		
	}
}

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

using namespace std;
typedef long long ll;
typedef pair<char,ll> P;
#define a first
#define b second
#define sz size()
#define pb(x) push_back(x) 
#define bg begin()
#define ed end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define mp(x,y) make_pair(x,y)
const ll MOD=1000000007;

vector<ll> pw2(51,1); vector<ll> pw10(19,1);
ll maxx(ll x,ll y,ll z){return max(max(x,y),z);}
ll minn(ll x,ll y,ll z){return min(min(x,y),z);}
ll mid(ll x,ll y,ll z){return x>y?y>=z?y:min(z,x):x>=z?x:min(y,z);}
ll gcd(ll x,ll y){if(x%y==0) return y;else return gcd(y,x%y);}
ll lcm(ll x,ll y){return x*(y/gcd(x,y));}
ll myceil(ll x,ll y){if(x<=y) return 1;else if(x%y==0) return x/y;else return x/y+1;}

int main(){
    string s,t; cin>>s>>t;
    ll ans=0,tmp=0;
    vector<set<ll>> que(26);
    rep(i,s.sz){
        ll tmpa=s[i]-'a';
        que[tmpa].insert(i+1);
    }
    rep(i,t.sz){
        ll S=t[i]-'a';
        if(que[S].sz==0){
            cout<<-1;
            return 0;
        }

        auto itr=que[S].upper_bound(tmp);
        if(itr==que[S].ed){
            ans+=(s.sz-tmp+*(que[S].bg));
            tmp=*(que[S].bg);
        }else{
            ans+=(*itr-tmp);
            tmp=*itr;
        }
    }
    cout<<ans;
}
		
	


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

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

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

int main()
{
    int N, A;
    cin >> N >> A;
    cout << N * N - A << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define sz(x) int(x.size())
#define pb push_back
#define eb emplace_back
using ll=long long;
using P = pair<ll,int>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
const ll MOD=1000000007,MOD2=998244353;



int main() {
    int N,X;
    cin>>N>>X;
    vector<int> L(N);
    rep(i,N)cin>>L.at(i);
    int now=0,count=1;
    rep(i,N){
        now+=L.at(i);
        if(now<=X)count++;
    }
    cout<<count<<endl;
}

Measured memory_bytes: 256
"""
author : halo2halo
date : 4, Feb, 2020
"""

import sys

# import itertools
# import math
# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

U = readline().decode('utf8').strip()

print('x'*len(U))


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

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

  bool flag = true, t = true;
  for(int i=0; i<3; i++){
    if(s[i] == 'R')  flag = false;
    else t = false;
  } 
  if(flag){
    cout << '0' << endl;
    return 0;
  }else if(t){
    cout << '3' << endl;
    return 0;
  }
  int ans = 1;
  if(s[1]=='R' && (s[0]=='R' || s[2]=='R'))
    ans = 2;

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


Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

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

ll lcm(ll a, ll b) {
	return a / gcd(a, b) *b;
}

struct edge {
	ll ind;
	ll to;
	ll d;
};


///////////////////////////



int main() {

	ll N, K, X, Y;
	cin >> N >> K >> X >> Y;

	ll ans = 0;

	repn(i, N) {
		if (i <= K) { ans += X; }
		else { ans += Y; }
	}

	cout << ans;

	system("PAUSE");
}


Measured memory_bytes: 504
N, x = map(int, input().split())
if 2*N-x>2 and x>2 and N>2:
  print('Yes')
  ans = [x-2,x+1,x,x-1,x+2]
  ls = []
  for i in range(1,2*N):
    if i in ans:
      continue
    ls += [i]
  ans = ls[:len(ls)//2]+ans+ls[len(ls)//2:]
  print('\n'.join(map(str, ans)))
  
elif 2*N-x>2 and x>1 and N>2:
  print('Yes')
  ans = [x+1,x,x-1,x+2]
  ls = []
  for i in range(1,2*N):
    if i in ans:
      continue
    ls += [i]
  ans = ls[:len(ls)//2+1]+ans+ls[len(ls)//2+1:]
  print('\n'.join(map(str, ans)))
elif 2*N-x>1 and x>2 and N>2:
  print('Yes')
  ans = [x-1,x,x+1,x-2]
  ls = []
  for i in range(1,2*N):
    if i in ans:
      continue
    ls += [i]
  ans = ls[:len(ls)//2+1]+ans+ls[len(ls)//2+1:]
  print('\n'.join(map(str, ans)))
elif N==2:
  if x==2:
    print('Yes')
    print(1,2,3,sep='\n')
  else:
    print('No')
else:
  print('No')

Measured memory_bytes: 27284
#include <math.h>
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
using std::string;

int main(void) {
    string str;
    cin >> str;
    int nine = 0;
    for(char c : str) {
        int n = c - '0';
        nine = (nine + n) % 9;
    }
    if(nine == 0) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3740
#include<bits/stdc++.h>
#define MIN -1000000
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
bool visited[100005];
const int max_N=1e5+10;
int H,W,h,w;
int board[105][105];
int mxindex,mxchain=0;
int main(void)
{
  string s;
  cin >> s;
  int ans=0;
  int tmp=0;
  for (int i = 0; i < int(s.size()); ++i)
    {
      if(s[i]=='A' || s[i]=='C' || s[i]=='G' || s[i]=='T')
	{
	  tmp++;
	  ans=max(ans,tmp);
	}
      else
	{
	  ans=max(ans,tmp);
	  tmp=0;
	}
    }
  ans=max(ans,tmp);
  cout << ans << endl;
  return 0;
}


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

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

int main()
{
    int n,k;
    cin>>n>>k;
    int arr[n+1];
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    cout<<solve(n,k,arr);

    return 0;
}

Measured memory_bytes: 1024
#include<cstring>
#include<string>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<complex>
#include<sstream>
#include<climits>
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int MAX_N = 1e5;
const ll INF = 1e18;
int N;
int a[MAX_N];
char op[MAX_N];
ll dp[MAX_N][3];


int main() {
  cin >> N;
  op[0] = '+';
  cin >> a[0];
  for (int i = 1; i < N; ++i) {
    char c;
    cin >> op[i] >> a[i];
  }

  dp[0][0] = a[0]; dp[0][1] = -INF; dp[0][2] = -INF;
  for (int i = 1; i < N; ++i) {
    if (op[i] == '+') {
      dp[i][0] = max(dp[i-1][0] + a[i], max(dp[i-1][1] - a[i], dp[i-1][2] + a[i]));
      dp[i][1] = max(dp[i-1][1] - a[i], dp[i-1][2] + a[i]);
      dp[i][2] = dp[i-1][2] + a[i];
    } else {
      dp[i][0] = max(dp[i-1][0] - a[i], max(dp[i-1][1] + a[i], dp[i-1][2] - a[i]));
      dp[i][1] = max(dp[i-1][0] - a[i], max(dp[i-1][1] + a[i], dp[i-1][2] - a[i]));
      dp[i][2] = max(dp[i-1][1] + a[i], dp[i-1][2] - a[i]);
    }
  }

  cout << dp[N-1][0] << endl;

  return 0;
}


Measured memory_bytes: 3200
#include <bits/stdc++.h>
using  namespace std;
#define ll    long long int
#define pai     pair<int,int>
#define vi      vector<int>
#define vd      vector<double>
#define mpi     map<int,int>
#define mps     map<string,int>
#define sti     stack<int>
#define stc     stack<char>
#define sei     set<int>
#define ses     set<string>
#define multii  multiset<int>
#define forn    for(int i=0;i<n;i++)

 int main()
{

int arr1[]={2,4,5,7,9};
int arr2[]={0,1,6,8};
int arr3[]={3};
string s;
cin>>s;
int r=s[s.size()-1]-'0';
if(r==2||r==4||r==5||r==7||r==9){
  cout<<"hon"<<endl;
}
else if(r==0||r==1||r==6||r==8){
  cout<<"pon"<<endl;
}

else if(r==3){
  cout<<"bon"<<endl;
}


}






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

int main(){
  int n;
  cin>>n;
  int a[3],mi=100000000;
  for(int i=0;i<n;i++)cin>>a[i],mi=min(a[i],mi);
  for(int i=1;i<=mi;i++){
    int cnt=0;
    for(int j=0;j<n;j++)  if(a[j]%i==0)cnt++;
    if(cnt==n) cout<<i<<endl;
  }
    

  
  return 0;
}

Measured memory_bytes: 1164
import java.util.*;

class Main{
	public static void main(String[] $){
		System.err.println();
		Scanner s=new Scanner(System.in);
		int n=s.nextInt(),k=s.nextInt();
		int[] a=new int[n];
		Arrays.setAll(a,i->s.nextInt());

		PriorityQueue<Integer> q=new PriorityQueue<>();
		int v=0;
		for(int l=0;l<=Math.min(n,k);++l){
			for(int r=0;l+r<=Math.min(n,k);++r){
				q.clear();
				for(int i=0;i<l;++i)
					q.add(a[i]);
				for(int i=0;i<r;++i)
					q.add(a[n-1-i]);
				for(int i=k-l-r;i>0&&!q.isEmpty()&&q.peek()<0;--i)
					q.poll();
				v=Math.max(v,q.stream().mapToInt(i->i).sum());
			}
		}
		System.out.println(v);
	}
}


Measured memory_bytes: 29012
n,y = map(int,input().split())
flag = False
for i in range(n+1):
    for j in range(n-i+1):
        if y == 10000*i + 5000*j + 1000*(n-i-j):
            flag = True
            print(i,j,n-i-j)
            break
    if flag:
        break
if not flag:
    print(-1,-1,-1)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
using namespace std;
string s;
string alphabet = "abcdefghijklmnopqrstuvwxyz";
bool ans = false;
int main() {
	cin >> s;
	for (int i = 0; i < 26; i++) {
		bool found = false;
		for (int j = 0; j < s.length(); j++) {
			if (s[j] == alphabet[i])
				found = true;
		}
		if (!found) {
			cout << alphabet[i] << endl;
			ans = true;
			break;
		}
	}
	if (!ans)
		cout << "None" << endl;
}

Measured memory_bytes: 512
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
char data[110][110];
int c;
int m,n;
void dfs(int x,int y,char ch) {
	data[x][y]='.';
	if(x-1>=0&&data[x-1][y]==ch) {
		dfs(x-1,y,ch);
	}

	if(x+1<n&&data[x+1][y]==ch) {
		dfs(x+1,y,ch);
	}

	if(y-1>=0&&data[x][y-1]==ch) {
		dfs(x,y-1,ch);
	}

	if(y+1<m&&data[x][y+1]==ch) {
		dfs(x,y+1,ch);
	}
}

int main() {

	while(scanf("%d%d",&n,&m)!=EOF) {
		if(m==0&&n==0) break;
		int a,b;
		c=0;
		for(int i=0; i<n; i++)
			for(int j=0; j<m; j++)
		scanf("\n%c",&data[i][j]);
//				cin>>data[i][j];
		for(int i=0; i<n; i++)
			for(int j=0; j<m; j++) {
				if(data[i][j]!='.') {
					c++;
					dfs(i,j,data[i][j]);
				}

			}
		printf("%d\n",c);



	}
	return 0;
}



Measured memory_bytes: 3560
N = int(input())
C = []
S = []
F = []

for _ in range(N - 1):
	tmp = list(map(int, input().split()))
	C.append(tmp[0])
	S.append(tmp[1])
	F.append(tmp[2])

for i in range(N):
	t = 0
	for j in range(i, N - 1):
		if t < S[j]:
			t = S[j]
		elif t % F[j] != 0:
			t += F[j] - (t % F[j])
		t += C[j]
	print(t)


Measured memory_bytes: 3064
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = [-i for i in a]
heapq.heapify(b)
for i in range(m):
	c = heapq.heappop(b)
	c *= -1
	c //= 2
	heapq.heappush(b,-c)
s = -sum(b)
print (s)

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

N,X,M=map(int,input().split())
LIST=[X]
SET={X}

a=X

while True:
    if a*a%M in SET:
        break
    else:
        a=a*a%M
        LIST.append(a)
        SET.add(a)

l=LIST.index(a*a%M)
LEN=len(LIST)

if N<=LEN:
    print(sum(LIST[:N]))
else:
    ANS=sum(LIST[:l])
    N-=l
    LIST=LIST[l:]
    S=sum(LIST)

    r,q=divmod(N,len(LIST))

    print(ANS+S*r+sum(LIST[:q]))
    



Measured memory_bytes: 13436
#include <bits/stdc++.h>
#define FOR(i,a,b) for(ll i=a; i<ll(b); i++) 
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int gcd(int a, int b){ //a>=0,b>=0,￢(a=b=0)
  while(min(a,b)>0){if(a<b)swap(a,b);a=a%b;}return max(a,b);
}
//int:~2e9   小数:double
int main(){
  int n,m;
  cin >>n>>m;


  if(n==m) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define N 1000000007
typedef long long ll;
#define all(v) (v).begin(),(v).end()
#define sz(x) int(x.size())

    
int main(){
	ll n;
	cin>>n;
	int a=1;
	for(int k=sqrt(n);k>=2;k--){
		if(n%k==0){
			a=k;
			break;
		}
	}
	ll ans=a+n/a-2;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256