akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
// #define _GLIBCXX_DEBUG
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(c) begin(c), end(c)

int n, m, h, k;
vector<int> b;
vector<int> srcx, srcy;
vector<int> s;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n >> m >> h >> k && n) {
        s.resize(n);
        for (size_t i = 0; i < n; i++) {
            cin >> s[i];
        }
        b.resize(m);
        vector<pair<int, int>> p(m);
        for (size_t i = 0; i < m; i++) {
            int x, y;
            cin >> x >> y;
            p[i] = make_pair(y, x);
        }
        sort(p.begin(), p.end());
        for (size_t i = 0; i < m; i++) {
            b[i] = p[i].second - 1;
        }
        vector<int> cur(n);
        for (size_t i = 0; i < n; i++) {
            cur[i] = i;
        }
        srcx.resize(m); srcy.resize(m);
        for (size_t i = 0; i < m; i++) {
            srcx[i] = cur[b[i]];
            srcy[i] = cur[b[i] + 1];
            swap(cur[b[i]], cur[b[i] + 1]);
        }
        vector<int> dst(n);
        for (size_t i = 0; i < n; i++) {
            dst[cur[i]] = i;
        }
        int org = 0;
        for (size_t i = 0; i < k; i++) {
            org += s[dst[i]];
        }
        int ans = org;
        for (size_t i = 0; i < m; i++) {
            int a = srcx[i];
            int b = srcy[i];
            if (a > b) swap(a, b);
            if (a < k && b >= k) {
                ans = min(ans, org - s[dst[a]] + s[dst[b]]);
            }
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 5020
n = int(input())
a = [int(x) for x in input().split()]

flag = 0
cnt = 1

for i in range(n-1):
    if a[i] < a[i+1] and flag == 0:
        flag = 1
    elif a[i] > a[i+1] and flag == 0:
        flag = 2
    elif flag == 1 and a[i] > a[i+1]:
        cnt += 1
        flag = 0
    elif flag == 2 and a[i] < a[i+1]:
        cnt += 1
        flag = 0

print(cnt)

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

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ld PI = 3.14159265359;

const ll MOD = (ll) 1e9 + 7;
const ll MAXN = (ll) 2e5 + 10;
const ll INF = (ll) 2242545357980376863;
const ld EPS = (ld) 1e-8;

ll dp[MAXN], B[MAXN], sm[MAXN];
vector<ll> C;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> B[i];
	C.pb(-1);
	ll l = -1;
	for(int i = 1; i <= n; i++){
		if(B[i] != l) C.pb(B[i]);
		l = B[i];
	}
	ll m = C.size() - 1;
	dp[0] = 1;
	for(int i = 1; i <= m; i++){
		sm[C[i]] += dp[i - 1];
		dp[i] = sm[C[i]];
		sm[C[i]] %= MOD;
		dp[i] %= MOD;
	}
	cout << dp[m];
	return 0;
}


/*

                                 ____              ,----..               ,----..
   ,---,                       ,'  , `.           /   /   \             /   /   \
  '  .' \                   ,-+-,.' _ |          /   .     :           /   .     :
 /  ;    '.              ,-+-. ;   , ||         .   /   ;.  \         .   /   ;.  \
:  :       \            ,--.'|'   |  ;|        .   ;   /  ` ;        .   ;   /  ` ;
:  |   /\   \          |   |  ,', |  ':        ;   |  ; \ ; |        ;   |  ; \ ; |
|  :  ' ;.   :         |   | /  | |  ||        |   :  | ; | '        |   :  | ; | '
|  |  ;/  \   \        '   | :  | :  |,        .   |  ' ' ' :        .   |  ' ' ' :
'  :  | \  \ ,'        ;   . |  ; |--'         '   ;  \; /  |        '   ;  \; /  |
|  |  '  '--'          |   : |  | ,             \   \  ',  /          \   \  ',  /
|  :  :                |   : '  |/               ;   :    /            ;   :    /
|  | ,'                ;   | |`-'                 \   \ .'              \   \ .'
`--''                  |   ;/                      `---`                 `---`
                       '---'

*/


Measured memory_bytes: 6640
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use itertools::Itertools;
use proconio::{input, marker::*};
use superslice::*;
fn main() {
    input! {
        k: usize,
        a: usize, b: usize,
    }
    let min = (a/k) * k;
    let max = (b/k) * k;

    if min == a {
        println!("OK");
    } else if a<= max && max <= b {
        println!("OK");
    } else {
        println!("NG");
    }
}


Measured memory_bytes: 2084
#include<stdio.h>
long long int h[100005];
int l;
void swap_h(int a, int b)
{
	long long int f = h[a];
	h[a] = h[b];
	h[b] = f;
	return;
}
int comp_h(int a, int b, int q)
{
	if (h[a] > h[b])return q;
	else return -1 * q;
}
void f1(long long int n, int q)
{
	h[l] = n;
	int now = l;
	l++;
	while (now > 0)
	{
		if (comp_h((now - 1) / 2, now, q) > 0)
			swap_h((now - 1) / 2, now);
		now = (now - 1) / 2;
	}
	return;
}
void f2(int q)
{
	l--;
	h[0] = h[l];
	int now = 0;
	for (;;)
	{
		if (2 * now + 2 < l)
		{
			if (comp_h(2 * now + 1, 2 * now + 2, q) > 0)
			{
				if (comp_h(now, 2 * now + 2, q) > 0)
					swap_h(now, 2 * now + 2);
				now = 2 * now + 2;
			}
			else
			{
				if (comp_h(now, 2 * now + 1, q) > 0)
					swap_h(now, 2 * now + 1);
				now = 2 * now + 1;
			}
		}
		else if (2 * now + 1 < l)
		{
			if (comp_h(now, 2 * now + 1, q) > 0)
				swap_h(now, 2 * now + 1);
			now = 2 * now + 1;
		}
		else
			break;
	}
	return;
}
int main()
{
	int n;
	scanf("%d", &n);
	int i;
	long long int a[300005];
	for (i = 0; i < 3 * n; i++)
		scanf("%lld", &a[i]);
	long long int sum = 0;
	l = 0;
	long long int b[100005];
	for (i = 0; i < n; i++)
	{
		sum += a[i];
		f1(a[i], 1);
	}
	for (i = 0; i <= n; i++)
	{
		b[i] = sum;
		if (h[0] < a[i + n])
		{
			sum -= h[0];
			f2(1);
			sum += a[i + n];
			f1(a[i + n], 1);
		}
	}
	l = 0;
	sum = 0;
	for (i = 0; i < n; i++)
	{
		sum += a[2 * n + i];
		f1(a[2 * n + i], -1);
	}
	for (i = 0; i <= n; i++)
	{
		b[n - i] -= sum;
		if (h[0] > a[2 * n - i - 1])
		{
			sum -= h[0];
			f2(-1);
			sum += a[2 * n - i - 1];
			f1(a[2 * n - i - 1], -1);
		}
	}
	long long int ans = b[n];
	for (i = 0; i < n; i++)
		if (ans < b[i])
			ans = b[i];
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
const int N=10000+10;
char dp[N][N];
bool vis[N];
int n,m,a[100],v[100];

void prework() {
	v[1]=2; v[2]=5; v[3]=5; v[4]=4; v[5]=5;
	v[6]=6; v[7]=3; v[8]=7; v[9]=6;
}

char tmp[N];
char* work(int x) {
	if (vis[x]) return dp[x];
	
	vis[x]=1;
	strcpy(dp[x],"\0");
	for (int i=1;i<=m;i++) {
		if (x<v[a[i]]) continue;
		if (!vis[x-v[a[i]]]) work(x-v[a[i]]);
		if (x-v[a[i]] && dp[x-v[a[i]]][0]=='\0') continue;
		
		char t[10]; t[0]='0'+a[i]; t[1]='\0';
		strcpy(tmp,t);
		strcat(tmp,dp[x-v[a[i]]]);
		if (strlen(tmp)>strlen(dp[x]) || strlen(tmp)==strlen(dp[x]) && strcmp(tmp,dp[x])>0) 
			strcpy(dp[x],tmp);
	}
	return dp[x];
}

int main()
{
	prework();
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++) scanf("%d",&a[i]);
	
	vis[0]=1; strcpy(dp[0],"\0");
	cout<<work(n);
	return 0;
}

Measured memory_bytes: 97152
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <numeric>
#include <iomanip>
#include <cmath>
using namespace std;
int main(void){
    string S;
    cin >> S;
    int Q;
    cin >> Q;
    bool reversed = false;
    string front;
    for(int i = 0; i < Q; i++){
        int T;
        cin >> T;
        if(T == 1){
            reversed = !reversed;
        } else {
            int F;
            char C;
            cin >> F >> C;
            if(!reversed){
                if(F == 1){
                    front.push_back(C);
                } else {
                    S.push_back(C);
                }
            } else {
                if(F == 2){
                    front.push_back(C);
                } else {
                    S.push_back(C);
                }
            }
        }
    }
    if(!reversed){
        reverse(front.begin(), front.end());
        cout << front + S << endl;
    } else {
        reverse(S.begin(), S.end());
        cout << S + front << endl;
    }
    return 0;
}

Measured memory_bytes: 1248
A = [list(map(int, input().split())) for _ in range(3)]

N = int(input())
for _ in range(N):
    is_matched = False
    b = int(input())
    for row in range(3):
        for col in range(3):
            if A[row][col] == b:
                is_matched = True
                A[row][col] = True
                if A[row][0] == True and A[row][1] == True and A[row][2] == True:
                    print('Yes')
                    exit()
                elif A[0][col] == True and A[1][col] == True and A[2][col] == True:
                    print('Yes')
                    exit()
                elif A[0][0] == True and A[1][1] == True and A[2][2] == True:
                    print('Yes')
                    exit()
                elif A[0][2] == True and A[1][1] == True and A[2][0] == True:
                    print('Yes')
                    exit()
                break
        if is_matched:
            break
print('No')

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


  
int main(){
  long n,m,count;
  cin >> n;
  vector<int> v(n);
  count = 1;
  if(n>1){
  for(long i ; i < n ; i++){
    cin >> v.at(i);
  }
  m = v.at(1);
  for(long j = 1; j < n; j++){
    if(v.at(j) >= v.at(j-1)){
      m = v.at(j);
      count++;
    }
    if(v.at(j) < v.at(j-1))
       v.at(j) = v.at(j-1);
  }
  }
  cout << count << endl;
      }

Measured memory_bytes: 256
#include <fstream>
#include <numeric>
#include <unordered_set>
#include <sstream>
#include <cassert>
#include <tuple>
#include <iomanip>
#include <random>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <chrono>
#include <stack>
#include <string>
#include <bitset>
#include <unordered_map>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>

#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x.size())
#define pb push_back
#define ll long long
#define int long long
#define pii pair <int, int>
#define print(x) for(auto it : x) cout << it << ' ';

using namespace std;

const int N = (int)(1e6) + 322;
const int MAXN = (int)(1e7) + 100;
const int inf = (int)(1e18) + 322;
const int mod = 998244353;
const double eps = 1e-6;
#define endl "\n" // remove



signed main () {
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    int a, b, c; cin >> a >> b >> c;
    swap(a, b);
    swap(a, c);
    cout << a << ' ' << b << ' ' << c;
    return 0;
}


Measured memory_bytes: 256
N,K=map(int,input().split(' '))
nums=[0]*(10**5)
for i in range(N):
  a,b=map(int,input().split(' '))
  nums[a-1]+=b
s=0
for i in range(len(nums)):
  s+=nums[i]
  if s>=K:
    print(i+1)
    break
  else:
    continue

Measured memory_bytes: 5744
#include <bits/stdc++.h>
#define int long
#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
int gcd(int a,int b){return b ? gcd(b,a%b) : a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}

main() {
    string S; cin >> S; string c;
    int a[4]; rep(i,4) a[i]=(int)S[i]-'0';
    for(int i=0;i<(1<<3);i++){
        int pos=a[0];
        for(int j=0;j<3;j++){
            if((i>>j)&1){
                c[j]='+'; pos+=a[j+1];
            }
            else {c[j]='-'; pos-=a[j+1];} 
        }
        if(pos==7) break;
    }
    rep(i,3) cout << a[i] << c[i];
    cout << a[3] << "=7" << endl; 

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<long>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using pii = pair<int, int>;
using pll = pair<long, long>;
#define fix20 cout << fixed << setprecision(20);
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define MOD 1000000007
#define all(vec) vec.begin(), vec.end()

int main(){
    long a,b,c;
    cin >> a >> b >> c;
    if(c - a - b <= 0) cout << "No" << endl;
    else if(4*a*b < (c-a-b)*(c-a-b)) cout << "Yes" << endl;
    else cout << "No" << endl;
  
    
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cassert>
#include<cmath>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;
 
int main()
{
  int Math,Greedy,Geometry,DP,Graph,Other;
  while(cin >> Math >> Greedy >> Geometry >> DP >> Graph >> Other,Math|Greedy|Geometry|DP|Graph|Other)
    {
      int total[3];
      total[0] = Math+DP;
      total[1] = Greedy+Graph;
      total[2] = Geometry+Other;
      assert(total[0]+total[1]+total[2] <= 100000000LL);
 
      //int Size = min(total[0],min(total[1],total[2]));
      int ans = 0;
         
      rep(i,3)
    {
      int A = total[0],B = total[1],C = total[2];
      int preans = i;
      A -= i;
      B -= i;
      C -= i;
      if(A<0 || B <0 || C<0)continue;
      preans += A/3;
      preans += B/3;
      preans += C/3;
      ans = max(ans,preans);
    }
 
      cout << ans << endl;
    }
  return 0;
}

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

int main(void){
	int n, m;
	int tmp;
	int sum_tarou, sum_hanako;
	bool frag;

	while(1){
		cin >> n >> m;
		if(n == 0 && m == 0){
			break;
		}

		int t_change = 101, h_change = 101;
		frag = true;
		vector<int> tarou;
		vector<int> hanako;

		for(int i = 0; i < n; i++){
			cin >> tmp;
			tarou.push_back(tmp);
		}
		for(int i = 0; i < m; i++){
			cin >> tmp;
			hanako.push_back(tmp);
		}
		sum_tarou = accumulate(tarou.begin(), tarou.end(), 0);
		sum_hanako = accumulate(hanako.begin(), hanako.end(), 0);

		int diff = sum_tarou - sum_hanako;
		if(diff % 2 != 0){
			cout << "-1" <<endl;
			continue;
		}

		for(auto itr = tarou.begin(); itr != tarou.end(); ++itr){
			vector<int>::iterator citer = find(hanako.begin(), hanako.end(), *itr - diff/2);
			if(citer != hanako.end()){
				frag = false;
				if(*itr + *citer < t_change + h_change){
					t_change = *itr;
					h_change = *citer;
				}
			}
		}
		if(frag){
			cout << "-1" << endl;
		}else{
			cout << t_change << " " << h_change << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3020
//
//  main.c
//  A_CookieExchanges
//
//  Created by user1 on 2017/05/06.
//  Copyright © 2017年 user1. All rights reserved.
//

#include <stdio.h>

#define PERSONS 3
#define LOGNUM 10000

int pocket[PERSONS] = {0};

typedef struct LOG {
    int log_pocket[3];
}Log;

Log logs[LOGNUM];
int logInd = 0;

//過去にこの状態を経験したことがないかをチェックする
int validCheck(){
    int ind_pocket;
    int ind_log;
    int ind_log_pocket;
    int hitCount = 0;
    
    int ret = 1;
    
    for(ind_pocket=0; ind_pocket< PERSONS; ind_pocket++){
        for(ind_log = 0; ind_log < LOGNUM; ind_log++){
            for (ind_log_pocket=0; ind_log_pocket<PERSONS; ind_log_pocket++) {
                if(pocket[ind_pocket] == logs[ind_log].log_pocket[ind_log_pocket]){
                    hitCount++;
                    goto find;
                }
            }
        }
    find:
        //一通りみてカブリがなかったら一度も来ていない状態
        if(hitCount == 0){ ret = 1; break;}
        //二つヒットがあったんなら、その時点で、3つしかない上に和は固定なので一度は来た状態だとわかる。
        else if(hitCount >= 2){ ret = -1; break;}
    }
    
    //登録
    logs[logInd].log_pocket[0] = pocket[0];
    logs[logInd].log_pocket[1] = pocket[1];
    logs[logInd].log_pocket[2] = pocket[2];
    
    return ret;
}

//クッキー交換して次の状態にする
int exchange(){
    int i;
    int next[3]={0};
    
    //奇数がないかチェックする
    for (i=0; i<PERSONS; i++) {
        if(pocket[i]%2 == 1){
            //printf("break! ODD_NUM\n");
            return -1;
        }
    }

    //次の状態を計算
    next[1] += pocket[0]/2;
    next[2] += pocket[0]/2;
    
    next[0] += pocket[1]/2;
    next[2] += pocket[1]/2;
    
    next[0] += pocket[2]/2;
    next[1] += pocket[2]/2;
    
    pocket[0] = next[0];
    pocket[1] = next[1];
    pocket[2] = next[2];
    
    //正常終了
    return 1;
}


void solve(){
    int count=0;
    validCheck();
    while(exchange() == 1){
        if(validCheck() == -1){
            printf("%d\n", -1);
            return;
        }
        count ++;
    
    }
    
    printf("%d\n", count);
}

int main(int argc, const char * argv[]) {
    scanf("%d %d %d", &pocket[0], &pocket[1], &pocket[2]);
    solve();
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
typedef pair<ll,ll> pr;
typedef vector<ll> vc;
typedef unordered_map<ll,ll> umap;
#define pb emplace_back
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define repr(i,a,b) for(ll i=a;i>=b;i--)
#define reps(i,v) for(ll i=0;i<v.size();i++)
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
const ll mod = 1e9+7;

int main(){
	ll n, k, a[105];
	bool dp[100005]={0};
	cin >> n >> k;
	rep(i,1,n) cin >> a[i];
	rep(i,1,k){
		rep(j,1,n){
			if(i < a[j]) break;
			if(!dp[i-a[j]]){
				dp[i] = true;
				break;
			}
		}
	}
	if(dp[k]) cout << "First" << endl;
	else cout << "Second" << endl;
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <algorithm>
#include <utility>
#include <functional>
#include <fstream>
#define debug(x) cout << #x << " = " << x << endl
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define repr(i,n) for(int i = (n); i > -1; i--)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const double EPS = 1e-9;


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

  string s;
  cin>>s;
  int w;
  cin>>w;
  rep(i, s.size()) {
    if(i % w == 0) {
      cout << s[i];
    }
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int int64_t
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define REPP(i, n) for (int i = 1; (i) < (int)(n+1); ++ (i))
#define REPR(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i, m, n) for(int i=(m)-1; i>=(n); i--)
#define ALL(v) v.begin(), v.end()
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())
#define SORTR(c) sort((c).begin(),(c).end(),greater<int>());
#define BIT(n) (1LL<<(n))
#define PCNT(x) __builtin_popcountll(x)
#define GCD(x,y) __gcd(x,y)
#define LCM(x,y) x/__gcd(x,y)*y
#define PB push_back
#define MP make_pair
#define endl "\n"
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
using namespace std;
using Graph = vector<vector<int> >;
using WeightedGraph = vector<vector<pair<int, int> > >;
typedef long double LD;
typedef vector<int> VI;
typedef vector<vector<int> > VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
const int INF = 2000000000;
const long double PI = acosl(-1);
const int MOD = 1000000007;
void print() {cout << endl;}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head; if (sizeof...(tail) != 0) cout << " ";print(forward<Tail>(tail)...);}
template <class T> void print(vector<T> &vec) {for (auto& a : vec) {cout << a; if (&a != &vec.back()) cout << " ";} cout << endl;}
template <class T> void print(vector<vector<T>> &df) { for (auto& vec : df) { print(vec);}}


void bfs(const vector<vector<int> > &G, int v, vector<int> &dist){
    for (int i = 0; i < (int) dist.size(); i++) dist[i] = -1;
    queue<int> que;
    dist[v] = 0;
    que.push(v);
    while (!que.empty()) {
        v = que.front();
        que.pop();
        for (int next_v : G[v]) {
            if (dist[next_v] != -1) continue;
            dist[next_v] = dist[v] + 1;
            que.push(next_v);
        }
    }
}


signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(10);
    int ans = 0;
    
    int N, M;
    cin >> N >> M;
    vector<int> H(N);
    vector<int> A(M), B(M);
    Graph G(N);
    REP (i, N) {
        cin >> H[i];
    }
    REP (i, M) {
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
        G[A[i]].PB(B[i]);
        G[B[i]].PB(A[i]);
    }
    int count = 0;
    int chk = 1;
    for (int v = 0; v < N; ++v) {
        chk = 1;
        for (int itr : G[v]) if (H[v] <= H[itr]) chk = 0;
        if (chk) count++;
    }
    cout << count << endl;


    
    
    
    return 0;
}

/*
cd ~/Desktop/Programming/AtCoder/contest/abc166/abc166_c && sh shellscripts/test_cpp.sh
cd ~/Desktop/Programming/AtCoder/contest/abc166/abc166_c && sh shellscripts/etest_cpp.sh
cd ~/Desktop/Programming/AtCoder/contest/abc166/abc166_c && sh shellscripts/submit_cpp.sh
*/


Measured memory_bytes: 11380
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<iomanip>
#include<sstream>
#include<map>
#include<cmath>
using namespace std;
#define rep(i,n) for(int i = 0;i < n;i++)
#define req(i,n) for(int i = 1;i <=n;i++)
#define rrep(i,n) for(int i = n -1;i >= 0;i--)
#define ALL(a) a.begin(),a.end()
typedef long long ll;
typedef long double ld;
const ll MOD =  1000000007;
const ll INF =  1LL << 60;
int n, m, x, y;ll z = 0, w, h, sum = 0, ans = 0,a,b,t,v;
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T & val) {
    std::fill((T*)array, (T*)(array + N), val);
}
int main(void) {
    cin >> a >> v >> b >> w >> t;
    if (w >= v) {
        cout << "NO" << endl;
        return 0;
    }
    h = abs(a -b);
    if(h <=(v - w) * t) cout << "YES"<<endl;
  else cout << "NO"<<endl;
}

Measured memory_bytes: 3596
#include<stdio.h>

#define N 100

int main(){
  int x,y,i,k;

  scanf("%d%d",&x,&y);

  
 
  if(x>y){
    k=x;
    x=y;
    y=k;
  }

  i=x%y;

  while(i!=0){
    x=y;
    y=i;
    i=x%y;
  }

  printf("%d\n",y);
    
  return 0;
}
    
		   
    



Measured memory_bytes: 2128
def inpl(): return [int(i) for i in input().split()]

N = int(input())
a = inpl()
A4 = A2 = A1 = 0
for i in range(N):
    if a[i] % 4 == 0:
        A4 += 1
    elif a[i] % 2 == 0:
        A2 = 1
    else:
        A1 += 1

if (A4+A2+A1)//2 <= A4:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 14252
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
int compare(const void *a,const void *b){
    if(*(int*)a>*(int*)b)return 1;
    return -1;
}
int main()
{   long long  a,b,k;
    scanf("%lld%lld%lld",&k,&a,&b);
    if(k<=a){
    printf("%lld",k+1);
    return 0;
    }
    if(a+2>=b){
        printf("%lld",k+1);
        return 0;
    }
    long long ans;
    if((k-a+1)%2==0){
        ans=(b-a)*(k-a+1)/2+a;
    }else{
        ans=(b-a)*(k-a)/2+1+a;
    }
    printf("%lld",ans);
    
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
//#define mp make_pair
#define pb push_back
#define int long long
#define pi 3.141592653589793238462643383279502
#define M 998244353
#define F first
#define S second
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
bool isPowerOfTwo(int n)
{
   if(n==0)
   return false;

   return (ceil(log2(n)) == floor(log2(n)));
}
int power(int x, unsigned int y)
{
    int res = 1;

    x = x;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x)%M;

        y = y>>1;
        x = (x*x)%M;
    }
    return res%M;
}
bool isprime(int x)
{
      if(x<2)
        return false;
    for(int i=2;i*i<=x;i++)
     {
        if (x%i==0)
            return false;
    }
    return true;
}
vector<pair<int,int>>primeFactors(int n)
{
    vector<pair<int,int>>v;
    int x=0;
    while (n % 2 == 0)
    {
        x++;
        n = n/2;
    }
    if(x>0)
    v.pb({2,x});
    for (int i = 3; i <= sqrt(n); i = i + 2)
    {
        int y=0;
        while (n % i == 0)
        {
            y++;
            n = n/i;
        }
        if(y>0)
        v.pb({i,y});
    }
    if (n > 2)
        v.pb({n,1});
    return v;
}
int maxSubArraySum(int a[], int size)
{
    int max_so_far = INT_MIN, max_ending_here = 0;

    for (int i = 0; i < size; i++)
    {
        max_ending_here = max_ending_here + a[i];
        if (max_so_far < max_ending_here)
            max_so_far = max_ending_here;

        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_so_far;
}
void solve()
{
string s;
cin>>s;
for(int i=0;i<s.size();i++)
{
    if(s[i]=='?')
        s[i]='D';
}
cout<<s<<endl;
}
signed main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
//cin>>t;
t=1;
while(t--)
{

solve();

}
}


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

#define int long long

main()
{
  int n;
  int s[105];
  int sum = 0;
  
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> s[i]; sum += s[i];
  }
  sort(s, s + n);
  if(sum % 10 != 0) cout << sum << endl;
  else {
    bool flg = false;
    for(int i = 0; i < n; i++) {
      if((sum - s[i]) % 10 != 0) {
	cout << sum - s[i] << endl;
	flg = true; break;
      }
    }
    if(!flg) cout << 0 << endl;
  }

  return (0);
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>
#include <random>
#include <complex>
#include <functional>
#include <tuple>
#include <new>

//#include "All.h"

using namespace std;

#define EPS (1e-9)
#define INF (1e9)
#define MOD (ll)(1e9 + 7)
#define PI (acos(-1))
#define REP(i,a,n) for(int i=a;i<n;i++)
#define rep(i, n) REP(i,0,n)
#define allof(a) (a).begin(), (a).end()

#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" ; "IMPOSSIBLE")

using ll = long long int;

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

ll beki(ll a, ll b) {
    ll tmp = 1;
    rep(i, b) tmp *= a;
    return tmp;
}

int main() {
    string S, T;
    cin >> S >> T;
    rep(i, S.length()) {
        if (S[i] != T[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

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

using namespace std;

const long long mod = 1e9 + 7;

int a[2010];

int main(){
	long long res = 0;
	int n;
	long long k;
	cin >> n >> k;
	for(int i = 0; i < n; ++i) cin >> a[i];
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n; j++){
			if(a[i] > a[j]){
				long long inv = k * (k + 1) / 2ll;
				res += inv % mod;
				res %= mod;
			}
			else if(a[i] < a[j]){
				long long cnt = k * (k - 1) / 2ll;
				res += cnt % mod;
				res %= mod;
			}
		}
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        sc.close();
        if (InputBad(S)) {
            System.out.println("Bad");
        } else {
            System.out.println("Good");
        }
    }
    public static boolean InputBad(String S) {
        if (S.length() < 2) {
            return false;
        }
        if (S.charAt(0) == S.charAt(1)) {
            return true;
        }
        return InputBad(S.substring(1));
    }
}


Measured memory_bytes: 21844
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#define REP(i, n) for(i=0; i<n; i++)
#define REPR(i, n) for(i=n; i>=0; i--)
#define FOR(i, m, n) for(i=m; i<n; i++)
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;

int main(void) {
    string s;
    cin >> s;
    ll cnt[26]={0};
    ll i;
    
    for(i=0; i<(ll)s.size(); i++) {
        cnt[s[i]-'a']++;
    }
    
    for(i=0; i<26; i++) {
        if(cnt[i]>=2) {
            cout << "no" << endl;
            return 0;
        }
    }
    cout << "yes" << endl;
    
    
    
    
}


Measured memory_bytes: 256
m, n = map(int, input().split())

def mod_binary(base, exponent, modulo):
  mask = 1 << (exponent.bit_length() - 1)
  ans = 1
  while mask:
    ans = ans * ans % modulo
    if exponent & mask:
      ans = ans * base % modulo
    mask >>= 1
  return ans

print(mod_binary(m, n, 1000000007))


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

public class Main{
  public static void main(String[] args)throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int m = Integer.parseInt(br.readLine());

    while(m-- > 0){
      String s = br.readLine();
      int len = s.length();
      HashSet<String> set = new HashSet<String>();

      for(int i=1;i<len;i++){
        String a = s.substring(0,i);
        String b = s.substring(i,len);
        String ra = new StringBuilder(a).reverse().toString();
        String rb = new StringBuilder(b).reverse().toString();

        set.add(a + b);
        set.add(a + rb);
        set.add(ra + b);
        set.add(ra + rb);
        set.add(b + a);
        set.add(b + ra);
        set.add(rb + a);
        set.add(rb + ra);
      }

      System.out.println(set.size());
    }
  }
}

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

int main()
{
  int n, x, min = 0;
  cin >> n >> x;
  vector<int> m(n);
  for(auto& x: m)
  {
    cin >> x;
    min += x;
  }
  sort(m.begin(), m.end());
  cout << ((x - min) / m[0]) + n << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long 
using namespace std;
int main()
{
	int w,a,b;cin>>w>>a>>b;
	if(a==b)cout<<0;
	else 
	{
		if(b>a+w)
		{
			cout<<b-a-w;
		}
		else if(a>b+w)cout<<a-b-w;
		else cout<<0;
	}
	
}

Measured memory_bytes: 256
def main():
    N = int(input())
    S = ""

    if N == 0:
        print("0")

    else:
        while N:
            if N % 2:
                N -= 1
                S = "1" + S

            else:
                S = "0" + S

            N //= -2

        print(S)

    return


main()


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll quick_m(int k)
{
    ll sum=5,ans=1;
    while(k)
    {
        if(k&1)
            ans*=sum;
        k=k>>1;
        sum=sum*sum;
    }
    return ans;
}
int main()
{
    ll n;
    cin>>n;
    if(n%2)
        cout<<0;
    else
    {
        ll ans=0;
        n=n/2;
        for(ll i=1; ; i++)
        {
            ll p=quick_m(i);
            if(p>n)
                break;
            ans+=n/p;
        }

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

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
  
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <unordered_set>
#include <list>
#include <tuple>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <cassert>
#include <numeric>
#include <cmath>
#include <bitset>
#include <random>
#include <regex>

using namespace std;
  
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define Fixed fixed << setprecision(14)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9+7; 
constexpr int mod2 = 998244353;
constexpr int dy[] = {0,1,0,-1,1,-1,-1,1};
constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
 
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class A, class B> inline A updiv(const A a,const B b){ return (a + b - 1) / b; }
template <class A, class B> inline A gcd(const A a,const B b){ return b ? gcd(b,a % b) : a; }
template <class A, class B> inline A lcm(const A a,const B b){ return a / gcd(a,b) * b; }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A,class B> using umap = unordered_map<A,B>;


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

    int k,n;
    cin >> k >> n;

    vector<int> a(n);

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

    int minv = LINF;
    rep(i,n){
        if(i == 0){
            chmin(minv, min(a[n-1] - a[i], a[i] + k - a[i+1]));
        }else if(i == n-1){
            chmin(minv, min(k - a[i] + a[i-1], a[i] - a[0]));
        }else{
            chmin(minv, min(a[i] + k - a[i+1], k - a[i] + a[i-1]));
        }
    }

    cout << minv << '\n';

    return 0;
  }

Measured memory_bytes: 1792
import random, math

def parse():
  return int(input())

def is_prime3(q,k=50):
    q = abs(q)
    #計算するまでもなく判定できるものははじく
    if q == 2: return True
    if q < 2 or q&1 == 0: return False

    #n-1=2^s*dとし（但しaは整数、dは奇数)、dを求める
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    
    #判定をk回繰り返す
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        #[0,s-1]の範囲すべてをチェック
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def main():
  N = parse()
  if N == 1:
    print(0)
    exit(0)
  elif is_prime3(N):
    print(1)
    exit(0)

  factors = factorization(N)
  
  factors_dict = {}
  for factor in factors:
    factors_dict[factor[0]] = factor[1]
  # print(factors_dict)

  ans = 0
  last_flag = False
  for p, e in factors_dict.items():
    # 素数ごとに繰り返す
    i = 1
    while e >= i:
      e -= i
      i += 1
      ans += 1
    
    # if e > 0:
    #   last_flag = True
  
  if last_flag:
    ans += 1
  print(ans)

if __name__ == "__main__":
  main()


Measured memory_bytes: 9588
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb(x) push_back(x)
#define mp make_pair
#define sz(x) ((int)(x).size())
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define all(x) x.begin(),x.end()
#define y1 omg
#define INF 1000000010
#define FOR(x, n) for(int x=0; x<n; x++)
#define ini(x, n) memset(x, n, sizeof(x));
#define MOD ((int)1e9 + 7)
#define atoi(x) ((x)-'0')
#define int ll
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

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

int a, b, c, d, ans = LLONG_MIN;
vi A, B;

signed main() {
	cin >> a >> b >> c >> d;
	A.pb(a); A.pb(b);
	B.pb(c); B.pb(d);
	if (a <= 0 && 0 <= b) A.pb(0);
	if (c <= 0 && 0 <= d) B.pb(0);
	for (auto i : A) for (auto j : B) {
		ans = max(ans, i * j);
	}
	cout << ans;
}

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

int main() {
  char w[3];
  int i,ans,tmp;
  ans = 0;
  tmp = 0;
  for(i = 0; i < 3; i++){
    cin >> w[i];
  }
  for(i = 0; i < 3; i++){
    if(w[i] == 'R'){
      ans++;
      if(tmp < ans){
        tmp = ans;
      }
    }
    else if(w[i] == 'S'){
      ans = 0;
    }
  }
  cout << tmp <<endl;
  return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b;
    cin >> a >> b;
    cout << 6 - a - b;
}


Measured memory_bytes: 256
n = int(input())
s = input()
z10 = [0 for _ in range(10)]
z100 = [0 for _ in range(100)]
z1000 = [0 for _ in range(1000)]
for i in range(n):
  x = int(s[i])
  for k in range(100):
    z1000[10*k+x] = z100[k]
  for j in range(10):
    z100[10*j+x] = z10[j]
  z10[x] = 1
print(sum(z1000))
#for i in range(1000):
  #if z1000[i] == 1:
    #print(i)

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

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, start, end) for(int i = start; i < end; i++)
#define all(x) (x).begin(), (x).end()
#define debug(x) cout << (x) << endl;
#define INF (1e9)
#define add_mod(a, b, x) ( (ll)(a) + (ll)(b) ) % (ll)(x)
#define mul_mod(a, b, x) ( ((ll)(a) % (ll)(x)) * ((ll)(b) % (ll)(x)) ) % (ll)(x)

ll sub_mod(ll a, ll b, ll x){
    ll tmp = (a - b) % x;
    if(tmp < 0) tmp += x;
    return tmp;
}

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

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

    int h, w;
    cin >> h >> w;

    vector<vector<char>> pic(h, vector<char>(w));
    rep(i, h){
        rep(j, w){
            cin >> pic[i][j];
        }
    }

    rep(i, w+2) cout << "#";
    cout << endl;
    rep(i, h){
        cout << "#";
        rep(j, w){
            cout << pic[i][j];
        }
        cout << "#" << endl;
    }
    rep(i, w+2) cout << "#";
    cout << endl;
}

Measured memory_bytes: 892
#include<stdio.h>

int main (){

  int N=0,sum=0,i=0;
  int L[200];

  
  scanf("%d",&N);

  for(int x=0;x<2*N;x++){
   
    scanf("%d",&L[x]);
    ++i;
  }

  for(int y=0;y<i+1;y++){
    for(int z=0;z<i-1;z++){
      if(L[z]<L[z+1]){
	sum=L[z];
	L[z]=L[z+1];
	L[z+1]=sum;
      }
    }
  }

  sum=0;

  for(int y=0;y<i;y+=2){
    sum+=L[y+1];
  }
  printf("%d\n",sum);

  return 0;
}

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

int main(){
  unsigned N=0;
  unsigned K=0,P=0;
  unsigned W=0;
  cin >> N;
  for(unsigned i=0;i<N;i++){
      cin >> K >> P;
      W=K%P;
      if(W!=0){
           cout << W << endl;
      }else{
           cout << P-W << endl;
     }
  }      
  return 0;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define drep(i,a,b) for(int i=(a); i>=(b);i--) 

const int maxn = 1e5 + 5;
const int MOD = 1e9 + 7;

multiset<int>q;
int a[maxn];

int main()
{
   ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
   int n; cin >> n;
   rep(i,1,n) cin >> a[i];
   rep(i,1,n){
      auto it = q.lower_bound(a[i]);
      if(it == q.begin())q.insert(a[i]);
      else{
          --it;
          q.erase(it);
          q.insert(a[i]);
      }
   }
   cout << q.size() << endl;
   return 0;
}

Measured memory_bytes: 5376
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string> //文字列
#include <iomanip> //doubleの桁数指定 setprecision()
#include <list> //前後に数値を入れれる配列
#include <map> //map
#include <vector> //vecror



#define REP(i,m,n) for(ll i = (ll) (m);i < (ll) (n);i++) //forの短縮
#define rep(i,n) REP(i,0,n) //REPが0の時
#define ll long long int

using namespace std;

double PI = acos(-1); //円周率

//常設関数↓

//最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

//最小公倍数
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}

//degree → radian
long double chg_DegRad(long double deg) {
	return deg * PI / 180.0;
}

//radian → degree
long double chg_RadDeg(long double rad) {
	return rad * 180.0 / PI;
}
 
//桁数
ll CountDigit(ll n) {
	ll digit = 1;
	while ((n /= 10) != 0) digit++;
	return digit;
}

//距離
double dis(double xa, double ya, double xb, double yb) {
	return pow(pow(xa - xb, 2.0) + pow(ya - yb, 2.0), 0.5);
}

//abs()平均
//pow(,)累乗


//提出コード↓

ll x,a,b;


int main() {
	cin >> x;
	a = x / 500;
	x %= 500;
	b = x / 5;
	cout << a * 1000 + b * 5 << endl;



	return 0;
}



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


int main() {
	string s, t, u;
	cin >> s >> t >> u;
	cout << s[0] << t[1] << u[2] << endl;
	return 0;
}


Measured memory_bytes: 256
function Main(input) {
  input = input.split("\n");
  var N = parseInt(input[0]);
  var A = input[1].split(" ").map(i => parseInt(i));
  var B = input[2].split(" ").map(i => parseInt(i));
  var sub = 0;
  var ans = 0;
  for(var i=0;i<N;i++){
    if(B[i]+sub-A[i]>=0){
      ans+=A[i];
      sub=Math.min(B[i]+sub-A[i],B[i]);
    }else{
      ans+=B[i]+sub;
      sub=0;
    }
  }
  ans+=Math.min(A[N],sub);

  console.log('%s', ans);
  return ans;
}

function debug(n){
  var input = document.getElementById("input"+n).value;
  var ans=Main(input);
  var result="WA";
  if(ans==document.getElementById("output"+n).value.split("\n")[0]){
    result="AC";
  }
  document.getElementById("result"+n).innerHTML=result;
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

bool valid(int j, int i, int N){
  if(j < 0 || j>=N)
    return false;
  else if(i < 0 || i>= N)
    return false;
  else
    return true;
}

int main(){
  int N;
  cin >> N;
  vector<int> P(N*N);
  int ans = 0;
  for(int i=0;i<N*N;i++)
    cin >> P.at(i);
  vector<int> score(N*N);
  vector<bool> end(N*N, false);
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      score.at(j*N+i) = min(min(j,N-j-1),min(i,N-i-1));
    }
  }
  int jval[4] = {0,0,1,-1};
  int ival[4] = {1,-1,0,0};
  int m[4] = {1,-1,N,-N};
  queue<int> que;
  for(int i=0;i<N*N;i++){
    ans += score.at(P.at(i)-1);
    end.at(P.at(i)-1) = true;
    que.push(P.at(i)-1);
    while(!que.empty()){
      int index = que.front();
      que.pop();
      int j = index/N;
      int i2 = index%N;
      for(int k=0;k<4;k++){
        if(valid(j+jval[k],i2+ival[k],N)){
          if(end.at(index)){
            if(score.at(index+m[k]) > score.at(index)){
              score.at(index+m[k]) = score.at(index);
              que.push(index+m[k]);
            }
          }else{
            if(score.at(index+m[k]) > score.at(index)+1){
              score.at(index+m[k]) = score.at(index)+1;
              que.push(index+m[k]);
            }
          }
        }
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 5372
#include<bits/stdc++.h>
using namespace std;
#define itn int

int main(void){
    int n;
    cin >> n;
    int a[n],A = 0;
    for(int i = 0;i < n;i++){
        cin >> a[i];
        A = A^a[i];
    }
    
    for(int i = 0;i < n;i++){
        cout << (int)(A^a[i]);
        if(i != n-1)cout << " ";
    }
}


Measured memory_bytes: 4340
import sys
from numba import njit
input = sys.stdin.buffer.readline

K = int(input())

A, B = map(int, input().split())


@njit
def main(K: int, A: int, B: int):
    for i in range(A, B + 1):
        if i % K == 0:
            print('OK')
            return 0
    print('NG')
    return 0


if __name__ == '__main__':
    main(K, A, B)


Measured memory_bytes: 108888
h, w = map(int, input().split())

if h == 1 or w == 1:
    print(1)
elif h % 2 == 0:
    print(int(h*0.5*w))
else:
    if w % 2 == 0:
        c = h * int(w * 0.5)
    else:
        c = 0.5 * (int(h * w) + 1)
    print(int(c))

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

int main() {
  int n,k;
  cin>>n>>k;
  vector<int> d(n);
  for(int i=0;i<k;i++){
    int m;
    cin>>m;
    for(int j=0;j<m;j++){
      int a;
      cin>>a;
      d[a-1]=1;
    }
  }
    int cnt=0;
    for(int i=0;i<n;i++){
      if(d[i]==0)cnt++;
    }
    cout<<cnt<<endl;
  }

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

const int size = 200;
const int limit = 1000001;
int dp[limit], dp_odd[limit];
int tetra[size], odd[size];

int main(void){
    int size_odd = 0;
    for(int i=1; i<size+1; ++i) {
        ll t = i*(i+1)*(i+2)/6;
        tetra[i-1] = t;
        if(t%2==1) {odd[size_odd]=t; size_odd++;}
    }
    int inf = numeric_limits<int>::max();
    rep(i, limit) dp[i] = dp_odd[i] = inf;
    dp[0] = 0;
    dp_odd[0] = 0;
    rep(i, size) {
        for(int j=tetra[i]; j<limit; ++j) 
            dp[j] = min(dp[j-tetra[i]]+1, dp[j]);
    }
    rep(i, size_odd) {
        for(int j=odd[i]; j<limit; ++j) 
            dp_odd[j] = min(dp_odd[j-odd[i]]+1, dp_odd[j]);
    }

    int n;
    while(cin >> n && n) {
        cout << dp[n] << " ";
        cout << dp_odd[n] << endl;
    }
}

Measured memory_bytes: 8972
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    R, G, B, N = il()
    rlimit = (N // R) + 1
    glimit = (N // G) + 1

    ret = 0
    for r in range(rlimit):
        for g in range(glimit):
            n = N - (R * r + G * g)
            if n > -1 and n % B == 0:
                ret += 1
    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 10112
#include <stdio.h>
int main(void) {
   int r, g, b;
   int total;
   
   scanf("%d",&r);
   scanf("%d",&g);
   scanf("%d",&b);
   
   total=r*100+g*10+b;
   
   if(total%4==0){
      printf("YES");
   }else{
      printf("NO");
   }
   
   
}

Measured memory_bytes: 128
#include<stdio.h>
 
int a[8],b[8],c[15],d[15];
char t[8][8];
 
int change(int y,int x){
  return 7-x+y;
}
 
int change2(int y,int x){
  return y+x;
}
 
int solve(int y){
  if(y==8)return 1;
  if(a[y])return solve(y+1);
  int x;
  for(x=0;x<8;x++){
    if(b[x])continue;
    if(c[change(y,x)])continue;
    if(d[change2(y,x)])continue;
    a[y]=1;
    b[x]=1;
    c[change(y,x)]=1;
    d[change2(y,x)]=1;
    t[y][x]='Q';
    if(solve(y+1))return 1;
    a[y]=0;
    b[x]=0;
    c[change(y,x)]=0;
    d[change2(y,x)]=0;
    t[y][x]='.';
  }
  return 0;
}
 
int main(){
  int i,j;
  for(i=0;i<8;i++)
    for(j=0;j<8;j++)
      t[i][j]='.';
 
  int N,y,x;
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d %d",&y,&x);
    a[y]=1;
    b[x]=1;
    c[change(y,x)]=1;
    d[change2(y,x)]=1;
    t[y][x]='Q';
  }
 
  solve(0);
 
  for(i=0;i<8;i++){
    for(j=0;j<8;j++){
      printf("%c",t[i][j]);
    }
    printf("\n");
  }
 
  return 0;
}

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

int main() {
  string s;
  cin>>s;
  int b_num = 0;
  long long ans = 0;
  for (auto c: s) {
    if (c == 'B') {
      ++b_num;
    } else {
      ans += b_num;
    }
  }
  cout<<ans<<endl;

}

Measured memory_bytes: 640