akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> store;

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

    for (int i = 0; i < N; i++) {
        int tmp;
        scanf("%d", &tmp);
        store.push_back(tmp);
    }

    int ans = abs(store[0] - X);
    for (int i = 1; i < (int)store.size(); i++) {
        int tmp = abs(store[i-1] - store[i]);
        ans = __gcd(ans, tmp);
    }

    cout << ans << endl;
}


Measured memory_bytes: 892
#include <bits/stdc++.h>
    using namespace std;
    #define pb push_back
    #define mod 1e18
    #define t 5e15
    typedef long long ll;
     
    __int128 power(__int128 a,__int128 b,ll k){
        __int128 res = 1;
        while(b>0){
            if(b&1) {
                res = (res * a);
            }
            if(res>=k || a>=k)
                return k;
            a = (a*a);
            b /= 2;
        }
        return res;
    }
    int main(){
        string s;
       	ll k;
        cin >> s >> k;
        for(int i=0;i<s.length();i++){
            //cout << k << endl;
            __int128 num = s[i]-'0';
            __int128 freq = power(num,ll(t),k);
            //cout << s[i] << " " << freq << endl;
            k -= freq;
            if(k<=0){
                cout << s[i];
                break;
            }
        }
    }

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
int mod=1e9+7;
int mod2=998244353;

int con(string s){
  int a=0;
  for(int i=0;i<s.size();i++){
    int x=1;
    if(s[i]>='2'&&s[i]<='9'){
      x=s[i]-'0';
      i++;
    }
    if(s[i]=='m')a+=1000*x;
    if(s[i]=='c')a+=100*x;
    if(s[i]=='x')a+=10*x;
    if(s[i]=='i')a+=1*x;
  }
  return a;
}

signed main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    string s1,s2;
    cin>>s1>>s2;
    int ans=con(s1)+con(s2);
    string s=to_string(ans);
    int x;
    for(int i=0;i<s.size();i++){
      if(s[i]>='2'&&s[i]<='9'){
        cout<<s[i];
      }
      if(s[i]!='0'){
        if(s.size()-i==4)cout<<"m";
        if(s.size()-i==3)cout<<"c";
        if(s.size()-i==2)cout<<"x";
        if(s.size()-i==1)cout<<"i";
      }
    }
    cout<<endl;
  }
}



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

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

    int n;
    cin >> n;
    int a[n][3];
    rep(i,n){
        rep(j,3){
            cin >> a[i][j];
        }
    }
    
    vector<vector<int>> dp(n+1, vector<int>(3,0));
    
    for(int i=1; i<n+1; i++){
        rep(j,3){
            rep(k,3){
                if(j==k) continue;
                dp[i][j] = max(dp[i][j], dp[i-1][k] + a[i-1][j]);
            }
        }
        // cout << i << "|" << dp[i][0] << "|" << dp[i][1] << "|" << dp[i][2] << endl;
    }
    
    int ans = 0;
    rep(i,3){
        ans = max(dp[n][i], ans);
    }
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 6912
S = input()
for i in range(2, len(S), 2):
    part_S = S[:-i]
    # print(part_S)
    mid = len(part_S) // 2
    left_S = part_S[:mid]
    right_S = part_S[mid:]
    if left_S == right_S:
        print(len(part_S))
        exit()


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

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

#define Canuc80k cin.tie(0); cout.tie(0);
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
#define I_AM ios_base::sync_with_stdio(0);
#define FORS(i,a,b,c) for (int i=a;i<=b;i+=c)
#define FORSD(i,a,b,c) for (int i=a;i>=b;i-=c)

const ll N = 1e6 + 1;
const ll M = 1e9 + 7;

int n, m;
ll a[N], f[N];

int main() {
    I_AM Canuc80k

    cin >> m >> n;
    
    FOR (i, 0, m) 
        f[i] = INT_MAX;

    FOR (i, 1, n) {
        cin >> a[i];
        f[a[i]] = 1;
    }

    f[0] = 0;
    FOR (i, 1, m) {
        FOR (j, 1, n) 
            if (i > a[j])
                f[i] = min(f[i], f[i - a[j]] + 1);
    }

    cout << f[m] << endl;
}


Measured memory_bytes: 3568
#include<stdio.h>
#include<string.h>
#define min(x,y) ((x) < (y) ? (x) : (y))
void swap(int* x, int* y){
  int l = *x;
  *x = *y;
  *y = l;
}

int main(){
  while(1){
    int n, m, h, k;
    int i, j;
    int last[1001], amida[1001][1001], now[1001], before[1001], change[100001][2];
    memset(amida, 0, sizeof(amida));
    scanf("%d%d%d%d", &n, &m, &h, &k);
    if(n == 0 && m == 0 && h == 0 && k == 0)return 0;
    for(i = 0;i < n;i++){
      scanf("%d", last + i);
      now[i] = i;
    }
    for(i = 0;i < m;i++){
      int a, b;
      scanf("%d%d", &a, &b);
      amida[b][a - 1] = 1;
    }
    int cnt = 0;
    for(i = 0;i <= h;i++){
      for(j = 0;j < n;j++){
	if(amida[i][j]){
	  swap(&now[j], &now[j + 1]);
	  change[cnt][0] = now[j];
	  change[cnt][1] = now[j + 1];
	  cnt++;
	}
      }
    }
    int none = 0;
    int ans = 0;
    for(i = 0;i < n;i++){
      before[now[i]] = i;
    }
    for(i = 0;i < k;i++){
      none += last[before[i]];
    }
    ans = none;
    for(i = 0;i < cnt;i++){
      int x = change[i][0];
      int y = change[i][1];
      if(x > y) swap(&x, &y);
      if(x >= k && y >= k)continue;
      if(x < k && y < k)continue;
      ans = min(ans, none - last[before[x]] + last[before[y]]);
    }
    printf("%d\n", ans);
  }
}

Measured memory_bytes: 5316
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int k = sc.nextInt();
    int a = sc.nextInt();
    int b = sc.nextInt();
    String s ="NG";
    for(int i = a; i <= b; i++) {
    	if(i % k == 0) {
          s ="OK";
          break;
        }
    }
    System.out.println(s);
  }
}

Measured memory_bytes: 35664
#include <stdio.h>
main(){
  int n,x,i,j,k;
  while(1){
    int sum=0;
    scanf("%d %d",&n,&x);
    if(n==0 && x==0)break;
    for(i=1;i<=n;i++){
      for(j=1+i;j<=n;j++){
	for(k=1+j;k<=n;k++){
	  if(x==j+i+k)sum++;
	}
      }
    }
    printf("%d\n",sum);
  }
  return 0;
}

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

const int maxn=100000;

struct Tree {
  int parent,left,right;
};

Tree tree[maxn]; int depth[maxn];

void print(int u) {
  cout<<"node "<<u<<": "<<flush;
  cout<<"parent = "<<tree[u].parent<<", "<<flush;
  cout<<"depth = "<<depth[u]<<", "<<flush;

  if (tree[u].parent==(-1)) {
    cout<<"root, "<<flush;
  }
  else if (tree[u].left==(-1)) {
    cout<<"leaf, "<<flush;
  }
  else {
    cout<<"internal node, "<<flush;
  }
  cout<<"["<<flush;
  for (int i=0,c=tree[u].left; c!=(-1); i++,c=tree[c].right) {
    if (i) {
      cout<<", "<<flush;
    }
    cout<<c<<flush;
  }
  cout<<"]"<<endl;
}
void Depth(int getu,int dpt) {
  depth[getu]=dpt;
  if (tree[getu].right!=(-1)) {
    Depth(tree[getu].right,dpt);
  }
  if (tree[getu].left!=(-1)) {
    Depth(tree[getu].left,dpt+1);
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  cout.tie(0);
  cin.tie(0);
  int n; cin>>n;
  for (int i=0; i<n; i++) {
    tree[i].parent=tree[i].left=tree[i].right=(-1);
  }
  int l;
  for (int j=0; j<n; j++) {
    int id,k; cin>>id>>k;
    for (int i=0; i<k; i++) {
      int c; cin>>c;
      if (i==0) {
        tree[id].left=c;
      }
      else {
        tree[l].right=c;
      }
      l=c;
      tree[c].parent=id;
    }
  }
  int x;
  for (int i=0; i<n; i++) {
    if (tree[i].parent==(-1)) {
      x=i;
    }
  }
  Depth(x,0);
  for (int i=0; i<n; i++) {
    print(i);
  }
  return 0;
}



Measured memory_bytes: 7868
#include <iostream>
#include <vector>
#include <stack>

using namespace std;
vector<int> g[101010];
int h[101010];

int main(){
    int v, e;
    cin >> v >> e;
    
    for (int i = 0; i < e; i++){
        
        int s, t;
        cin >> s >> t;
        
        g[s].push_back(t);
        h[t]++;
    }
    
    // 入次数0の頂点の集合
    
    stack<int> st;
    
    //　入次数0の頂点を追加する
    for (int i = 0; i < v; i++) {
        if (h[i] == 0) st.push(i);
    }
    
    vector<int> ans;
    
    while (st.size()){
        
        int i = st.top();
        st.pop();
        
        ans.push_back(i);
        
        for (auto &j : g[i]){
            
            h[j]--;
            
            if (h[j] == 0) st.push(j);
        }
    }
    
    for (int i : ans) cout << i << endl;
}


Measured memory_bytes: 5968
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
int A[100000], B[100000];

bool ok[100000];
int cur = 0;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    int N, Q; cin >> N >> Q;
    for(int i = 0; i < Q; i++) {
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }
    ok[1] = true;
    for(int i = 0; i < Q; i++){
        if(cur == A[i]) cur = B[i];
        else if(cur == B[i]) cur = A[i];
        if(ok[A[i]]) {
            if(!ok[B[i]]) ok[A[i]] = false;
            ok[B[i]] = true;
        }
        else if(ok[B[i]]) {
            if(!ok[A[i]]) ok[B[i]] = false;
            ok[A[i]] = true;
        }
        if(cur > 0) ok[cur-1] = true;
        if(cur < N-1) ok[cur+1] = true;
    }
    ok[cur] = true;
   
    int ans = 0;
    for(int i = 0; i < N; i++){
        if(ok[i]) {
            ans++;
        }
    }
    cout << ans << endl;
}

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

typedef long long ll;
int n;

int main()
{
    while(cin >> n && n) {
        ll ans = 0;
        while(n != 1) {
            ans++;
            n = (n % 2) ? n * 3 + 1 : n / 2;
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
int main() {
	int k, n;
	cin >> k >> n;
	vector<int>a(n); 
	rep(i, n) cin >> a[i];
	a.push_back(a[0] + k);
	int l = 0;
	rep(i, n) {
		l = max(l, a[i + 1] - a[i]);
	}
	int ans = k - l;
	cout << ans << endl;
	return (0);
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define debug(x) cout << " >> " << #x << " "<<x<<endl;
void Solve_Case()
{
     int n;
     cin >> n;
     int sum = (n)*(n-1)/2;
     cout << sum ;
}
signed main()
{
    int TestCases=1;

    while(TestCases--)
    {
        Solve_Case();
    }
	return 0;
}


Measured memory_bytes: 256
T=list(input())


ans=[]
buff="D"

leng=len(T)

for i in range(leng):
    now=T[i]
    if now=="?":
        if (i+1 < leng) and T[i+1] in ["?", "D"]:
            if buff == "P":
                buff="D"
            else:
                buff="P"
        else:
            buff="D"
    else:
        buff=now
    ans.append(buff)


print("".join(ans))

Measured memory_bytes: 88152
#include<iostream>
#include<string>
using namespace std;
int main (){
int n,m;
cin>>n>>m;
string str[10];
for(int i=0;i<n;i++){
 cin>>str[i];
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(str[i][j]=='#'){
for(int k=i+1;k<n;k++){
for(int l=0;l<j;l++){
if(str[k][l]=='#'){
 cout<<"Impossible"<<endl;
return 0;
}
}
}
for(int k=0;k<i;k++){
for(int l=j+1;l<m;l++){
if(str[k][l]=='#'){
 cout<<"Impossible"<<endl;
return 0;
}}}}}}
cout<<"Possible"<<endl;
return 0;
}


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

using namespace std;

int main()
{
    string S;
    cin >> S;
    int count = 0;
    for(int i=0;i<S.size() / 2;++i){
        if(S[i] != S[S.size() - 1 - i]){
            ++count;
        }
    }
    cout << count << endl;
}


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

def main():
    N,M,K = map(int,input().split())
    friend = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)
        
    brock = [[] for _ in range(N)]
    for _ in range(K):
        c,d = map(int,input().split())
        brock[c-1].append(d-1)
        brock[d-1].append(c-1)
        
    parent = [-1 for _ in range(N)]
    group = [0 for _ in range(N)]
    
    for i in range(N):
        put = []
        if parent[i] == -1:
            q = deque([i])
            parent[i] = i
            while q:
                now = q.pop()
                put.append(now)
                for fol in friend[now]:
                    if parent[fol] == -1:
                        parent[fol] = i
                        q.append(fol)
            l = len(put)
            for num in put:
                group[num] = l-1
                
        else:
            continue

    for i in range(N):
        group[i] -= len(friend[i])
        for dis in brock[i]:
            if parent[i] == parent[dis]:
                group[i] -= 1
    
    print(*group)
    
if __name__ == "__main__":
    main()


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

int main(){
  int n;
  cin >> n;
  
  int a[n];
  for(int i=0;i<n;i++){
    cin >> a[i];
    
  }
  int x=0;
  int y=0;
  while(x==0){
  	for(int j=0;j<n;j++){
      if(a[j]%2==1){
      	x=1;
      }
      a[j]=a[j]/2;
      
    }
    y++;
  }
  cout << y-1;
}

Measured memory_bytes: 3100
#include "bits/stdc++.h"
using namespace std;
#define INF 1e9
#define rep(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = (l); i < (r); i++)
#define ALL(x) (x).begin(), (x).end()     //昇順
#define RALL(x) (x).rbegin(), (x).rend()  // 降順
#define FOR(i, c) \
  for (__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
const long long mod = 1e9 + 7;
typedef long long ll;  // ll とdoubleは違う
typedef priority_queue<int> PQ;
typedef vector<long long> VL;
typedef vector<bool> VB;
typedef vector<int> VI;  // VI a(n);
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<char> VC;
typedef vector<VS> VSS;
typedef vector<VC> VCC;
typedef vector<VI> VII;  // VII a(n,vector<int>(m)) n * m
typedef vector<VL> VLL;
typedef pair<int, int> PII;
typedef map<int, int> MP;  // MP a;
typedef vector<pair<ll, ll>> PS;
template <class T, class U>  // chmax(max, a);
bool chmax(T &a, U b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T, class U>  // chmin(min,a)
bool chmin(T &a, U b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T>  // operator << (cout,a);
ostream &operator<<(ostream &os, vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) { os << v[i] << (i < v.size() - 1 ? ", " : ""); }
  os << "}";
  return os;
}

// g++ -std=c++11 prac.cpp

int main() {
  ll x=1,y=0,z=0,k,n,m,h,ans = 0,w,sum=0,Max=-1e9-1,cnt=0,Min=1e9 + 1;
  string s, t, u;
  bool ok=true;
  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;

long long int x;

int main()
{
    scanf("%lld", &x);

    if(x%11==0)printf("%lld", x/11*2);
    else if(x%11<=6)printf("%lld", x/11*2+1);
    else printf("%lld", x/11*2+2);

    return 0;
}


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

int main() {
  int H, W;
  while (true) {
    cin >> H >> W;
    if (H == 0 && W == 0) break;
    for (int i = 0; i < H; ++i) {
      for (int j = 0; j < W; ++j) {
        if (((i + j) % 2) == 0) cout << "#";
        else cout << ".";
      }
      cout << endl;
    }
    cout << endl;
  }

  return 0;
}


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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 1e5+50;
const int M = 1e6;
const ll oo = 1e18;
const int mod = 1e9+7;

string dp[3030];

int main(){
	string a,b;
	cin>>a>>b;
	int n = a.size();
	int m = b.size();
	for(int i=0;i<n;i++){
		string mx;
		for(int j=0;j<m;j++){
			string tmp = mx;
			if(dp[j].size() > mx.size())tmp = dp[j];
			if(a[i] == b[j]){
				if(mx.size() + 1 > dp[j].size())
				dp[j] = mx + a[i];
			}
			mx = tmp;
		}
	}
	string ans;
	for(int i=0;i<m;i++)if(dp[i].size() > ans.size())ans = dp[i];
	cout << ans << endl;

}

Measured memory_bytes: 11996
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  string t;
  cin >>s>>t;

  sort(s.begin(),s.end());
  sort(t.begin(),t.end());
  reverse(t.begin(),t.end());
  if(s < t){
      cout<<"Yes"<<endl;
  }else{
      cout<<"No"<<endl;
  }
return 0;
}

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

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    string s;
    cin >> s;
    string ans = "AC";
    int cnt = 0;
    if(s[0]!='A') ans = "WA";
    for(int i=1; i<s.length(); i++){
        if(isupper(s[i])){
            if(i==1 || i==s.length()-1 || s[i]!='C') ans = "WA";
            cnt++;
        }
    }
    if(cnt!=1) ans = "WA";
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
def souhei(a,b):
	c=int(a)
	d=int(b)
	return [c, d]
moji=input()
moji=list(moji)
P=int(input())
for pp in range(P):
	some=list(input().split())
	if some[0]=='print':
		some[1],some[2]=souhei(some[1],some[2])
		for a in range(some[1],some[2]+1):
			if a==some[2]:
				print(moji[a])
			else:
				print(moji[a],end='')
	elif some[0]=='reverse':
		some[1],some[2]=souhei(some[1],some[2])
		nn=0
		m=int((some[1]+some[2])/2)
		for bb in range(some[1],m+1):
			X=moji[bb]
			moji[bb]=moji[some[2]-nn]
			moji[some[2]-nn]=X
			nn+=1	
	elif some[0]=='replace':
		some[1],some[2] = souhei(some[1],some[2])
		g=some[3]
		g=list(g)
		n=0
		for oo in range(some[1],some[2]+1):
			moji[oo]=g[n]
			n+=1


Measured memory_bytes: 5744
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

def main():
    N = INT()
    A = LIST()
    B = LIST()
    C = LIST()
    sumv = 0
    for i in range(N):
        sumv += B[A[i]-1]
        if i > 0:
            if A[i] - A[i-1] == 1:
                sumv += C[A[i-1]-1]
    print(sumv)

if __name__ == '__main__':
    main()


Measured memory_bytes: 38384
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <cmath>
#include <list>
#include <iomanip>
#include <set>
#include <map>
#include <sstream>
#include <string.h>
#include <fstream>
#include <stdio.h>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int, int> PII;
typedef vector<int> VI;

#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define RFOR(i,a,b) for(int (i)=(a)-1;(i)>=(b);--(i))
#define MP make_pair
#define MOD 1000000007
#define INF 1000000001
#define PB push_back
#define eps 1e-5
#define X first
#define Y second

int n,a;
vector<int> v;
int PS[200000+47];
int prv[200000+47];

int main()
{
    cin >> n;
    FOR (i,0,n) {
        cin >> a;
        if (!v.size() || v.back() != a) {
            v.PB(a);
        }
    }
    
    PS[0] = 1;
    FOR (i,0,v.size()) {
        if (prv[v[i]] == 0) {
            PS[i+1] = PS[i];
        } else {
            PS[i+1] = (PS[i] + PS[prv[v[i]]])%MOD;
        }
        
        prv[v[i]] = i+1;
    }
    
    cout << PS[v.size()];
}

/*
 80000
 40694
 73594
 13614
 65544
 */


Measured memory_bytes: 2676
k,n=map(int,input().split())
house=list(map(int,input().split()))
dist=k-house[len(house)-1]+house[0]
for i in range(n-1):
    new_dist=house[i+1]-house[i]
    if dist<=new_dist:
        dist=new_dist
dist=k-dist
print(dist)

Measured memory_bytes: 26444
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main(){
    ll N,K;
    cin >> N >> K;
    vector<ll> A(N),F(N);
    for(int i=0;i<N;i++) cin >> A[i];
    for(int i=0;i<N;i++) cin >> F[i];
    sort(A.begin(),A.end());
    sort(F.begin(),F.end(),greater<ll>());
    ll l = -1,r = 1e12+1;
    auto check = [&](ll x){
        ll k = K;
        for(int i=0;i<N;i++){
            if(A[i]*F[i]>x){
                k -= (A[i]*F[i]-x+F[i]-1)/F[i];
                if(k<0) return false;
            }
        }
        return true;
    };
    while(l+1<r){
        ll m = (l+r)/2;
        if(check(m)) r = m;
        else l = m;
    }
    cout << r << endl;
}

Measured memory_bytes: 3456
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(obj)   (obj).begin(),(obj).end()

#define debug(var)  do{std::cout << __LINE__ << "> " << #var << ": ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

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

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

template<typename T>
struct CumulativeSum {
    vector<T> s;
    CumulativeSum(const vector<T> &nums) {
        int n = nums.size();
        s.resize(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + nums[i];
        }
    }
    // [l, r), l and r is 0-indexed.
    T sum(int l, int r) {
        return s[r] - s[l];
    }
};

void Main() {
	ll N, X, M; cin >> N >> X >> M;
	ll A = X % M;
	map<ll, ll> mp;
	vl ar;
	mp[A] = 0;
	ar.push_back(A);
	// [)
	int loop_start = -1;
	int loop_end = -1;
	FOR(i,1,N) {
		ll tmp = (A * A) % M;
		if (mp.count(tmp) != 0) {
			loop_start = mp[tmp];
			loop_end = i;
			break;
		} else {
			mp[tmp] = i;
		}
		A = tmp;
		ar.push_back(A);
	}
	CumulativeSum<ll> cs(ar);
	if (loop_end == -1 || N < loop_end) {
		cout << cs.sum(0, N) << endl;
	} else {
		ll tmp = N - loop_end;
		ll tmp2 = tmp / (loop_end - loop_start);
		ll tmp3 = tmp % (loop_end - loop_start);
		cout << cs.sum(0, loop_start) + cs.sum(loop_start, loop_end) * (tmp2 + 1) + cs.sum(loop_start, loop_start + tmp3) << endl;
	}
}

int main() {
    cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}


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

int main(){
  string s,t;
  cin >> s >> t;
  int ans = 0;
  if(s.at(0)==t.at(0)){
    ans++;
  }
  if(s.at(1)==t.at(1)){
    ans++;
  }
  if(s.at(2)==t.at(2)){
    ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
temp = gets.chomp.rstrip
count = 0
temp.size.times do |n|
	if n % 2 == 0
		count += 1 if temp[n] == '1'
	else
		count += 1 if temp[n] == '0'
	end
end

try = temp.size - count

puts try > count ? count : try

Measured memory_bytes: 1916
import itertools
n = int(input())
a = tuple(i for i in range(1, n+1))
x = tuple(map(int, input().split()))
y = tuple(map(int, input().split()))

for i, z in enumerate(tuple(itertools.permutations(a))):
    if z == x:
        x_count = i
    if z == y:
        y_count = i
print(abs(x_count - y_count))

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

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

int main(){
	int n,x ;
	cin >> n >> x ;
	int g ;
	for(int i=0;i<n;i++){
		int sub ; cin >> sub ;
		if(sub>x) sub = sub-x ;
		else sub = x-sub ;
		if(i==0) g = sub ;
		else g = gcd(g,sub) ;
	}
	cout << g << endl ;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll ;
 
ll M=1000000007;
ll a[2003],b[2003];
ll s[2002][2002];
int main()
{
    ll m,n; cin>>m>>n;
    for (int i=1; i<=m; i++) cin>>a[i];
    for (int i=1; i<=n; i++) cin>>b[i];
    
    s[0][0]=1;
    for (int i=1; i<=m; i++) s[i][0]=1;
    for (int j=1; j<=n; j++) s[0][j]=1;
    
    for (int i=1; i<=m; i++)
        for (int j=1; j<=n; j++)
        {
        	ll ans;
        	ans=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        	if (a[i]==b[j]) ans+=s[i-1][j-1];
        	ans%=M;
        	s[i][j]=ans;
		}
		
	if (s[m][n]<0) s[m][n]+=M;
	cout << s[m][n] << endl;
        
}

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;
struct Edge {
	ll to;
	ll cost;
};
using Graph = vector<vector<Edge>>;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define ALL(a) (a).begin(), (a).end()
#define RES(a, n) (a).resize(n)
#define VLCIN(a, n) REP(i,n){cin >> a[i];}
/***** define constant start *******/
const ll MOD = 1000000007;
const double PI = 2.0 * asin(1.0);
const ll INF = 1L<<60;
string abc = "abcdefghijklmnopqrstuvwxyz";
string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll MAX = (ll)pow(10,7);
/****** define constant end ********/
/****** define variable start ******/
ll n;
vl x, y;
Graph g;
/******* define variable end *******/
ll prim(ll n) {
    ll res = 0;
	vl d(n, INF); d[0] = 0;
	priority_queue<P, vector<P>, greater<P>> q;
	q.push(P(0, 0));
    while(q.size()){
		ll cost = q.top().first, v = q.top().second; q.pop();
		if(d[v] < cost) continue;
		res += cost; d[v] = -INF;
		for(ll i = 0; i < g[v].size(); i++){
			ll to = g[v][i].to, nxtcost = g[v][i].cost;
			if(d[to] > nxtcost){
				d[to] = nxtcost;
				q.push(P(nxtcost, to));
			}
		}
    }
    return res;
}
typedef pair<ll, ll> pair_t;

bool comp(const pair<ll, pair<ll, ll>> &a, const pair<ll, pair<ll, ll>> &b) { return a.first < b.first; }

void sort2vectors(
		vector<ll> &av,
		vector<pair<ll, ll>> &bv) { // ふたつの配列をまとめてそーと A[2,1] B[3,4] -> 1,4 2,3
	ll n = av.size();
	vector<pair<ll, pair<ll, ll>>> p(n);
	vector<ll> av2(n);
	vector<pair<ll, ll>> bv2(n);
	for (ll i = 0; i < n; i++)
		p[i] = make_pair(av[i], bv[i]);
	sort(p.begin(), p.end(), comp);
	for (ll i = 0; i < n; i++) {
		av2[i] = p[i].first;
		bv2[i] = p[i].second;
	}
	av = av2;
	bv = bv2;
}
int solve() {
	cin >> n;
	RES(x, n);
	RES(y, n);
	g.resize(n);
	vector<pair<ll, ll>> pa(n);
	vector<pair<ll, ll>> pa2(n);
	REP(i, n){
		cin >> x[i] >> y[i];
		pa[i] = make_pair(y[i], i);
		pa2[i] = make_pair(x[i], i);
	}
	sort2vectors(x, pa);
	REP(i, n-1){
		Edge e = {pa[i+1].second, x[i+1]-x[i]};
		g[pa[i].second].push_back(e);
		Edge e2 = {pa[i].second, x[i+1]-x[i]};
		g[pa[i+1].second].push_back(e2);
	}
	sort2vectors(y, pa2);
	REP(i, n-1){
		Edge e = {pa2[i+1].second, y[i+1]-y[i]};
		g[pa2[i].second].push_back(e);
		Edge e2 = {pa2[i].second, y[i+1]-y[i]};
		g[pa2[i+1].second].push_back(e2);
	}
	ll ans = prim(n);
	cout << ans << endl;
	return 0;
}
int main() {
	// clock_t start = clock();
	cout << std::fixed << std::setprecision(10);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int end_solve = solve();
	/*
	clock_t end = clock();
	const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC *
	1000.0; printf("time %lf[ms]\n", time);
	*/

	return end_solve;
}


Measured memory_bytes: 23360
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define A first
#define B second
#define db double
#define lowbit(p) (p&(-p))
using namespace std;
void read(int &x){
	x=0; char c=getchar(); int p=1;
	for (;c<48;c=getchar())if (c=='-')p=-1;
	for (;c>47;c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x*=p;
}
void read(ll &x){
	x=0; char c=getchar(); int p=1;
	for (;c<48;c=getchar())if (c=='-')p=-1;
	for (;c>47;c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x*=p;
}
void Min(int &x,int y){
	if (x>y)x=y;
}
void Max(int &x,int y){
	if (x<y)x=y;
}
void Min(ll &x,ll y){
	if (x>y)x=y;
}
void Max(ll &x,ll y){
	if (x<y)x=y;
}

map< pii,int >id;
#define M 600005
struct ed{
	int x,l,nx;
}e[M*3];
int nx[M],dis[M],n,m,ecnt=1;
bool mark[M];
priority_queue< pii >Q;
void add(int x,int y,int l){
	e[ecnt]=(ed){y,l,nx[x]};
	nx[x]=ecnt++;
}
void dij(int s,int t){
	memset(dis,63,sizeof(dis));
	Q.push(mp(dis[s]=0,s));
	int x;
	for (;!Q.empty();){
		x=Q.top().B; Q.pop();
		if (mark[x])continue;
		mark[x]=1;
		for (int i=nx[x];i;i=e[i].nx){
			if (dis[x]+e[i].l<dis[e[i].x]){
				dis[e[i].x]=dis[x]+e[i].l;
				Q.push(mp(-dis[e[i].x],e[i].x));
			}
		}
	}
	if (mark[t]){
		printf("%d\n",dis[t]);
	}
	else {
		printf("-1\n");
	}
}
int tot;
int get(int x,int y){
	if (id[mp(x,y)])return id[mp(x,y)];
	else return id[mp(x,y)]=++tot;
}
int main(){
// 	freopen("1.in","r",stdin);
	read(n); read(m);	
	int i,x,y,c;
	for (i=1;i<=m;i++){
		read(x); read(y); read(c);
		add(get(x,0),get(x,c),1);
		add(get(x,c),get(x,0),0);
		add(get(x,c),get(y,c),0);
		add(get(y,c),get(x,c),0);
		add(get(y,c),get(y,0),0);
		add(get(y,0),get(y,c),1);
	}
	dij(get(1,0),get(n,0));
	return 0;
}

Measured memory_bytes: 53752
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> Pl;
typedef pair<int, int> P;

ll a[100010*2], ans;
int n;

int main(){
    cin >> n;
    a[0] = 0;
    for(int i = 1; i < n+1; i++){
        cin >> a[i];
        a[i] += a[i-1];
    }
    sort(a, a+n+1);

    ll cou = 0;
    for(int i = 1; i < n+1; i++){
        if(a[i-1] == a[i])  ++cou;
        else{
            ans += (cou*(cou+1))/2;
            cou = 0;
        }
    }
    ans += cou*(cou+1)/2;
    cout << ans << endl;
}

Measured memory_bytes: 1920
//raja1999

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

//std::ios::sync_with_stdio(false);
int ans[100005];
vector<vi>adj(100005),edg(100005);
int deg[100005];
int dfs(int u,int p,int c){
	int i,col;
	col=1;
	rep(i,adj[u].size()){
		if(adj[u][i]!=p){
			if(col==c){
				col++;
			}
			ans[edg[u][i]]=col;
			dfs(adj[u][i],u,col);
			col++;
		}
	}
	return 0;
}
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t,t1;
	//cin>>t;
	t=1;
	t1=t;
	while(t--){
		int n,i,u,v,maxx=0;
		cin>>n;
		rep(i,n-1){
			cin>>u>>v;
			u--;
			v--;
			deg[u]++;
			deg[v]++;
			adj[u].pb(v);
			adj[v].pb(u);
			edg[u].pb(i);
			edg[v].pb(i);
			maxx=max(maxx,max(deg[u],deg[v]));
		}
		cout<<maxx<<endl;
		dfs(0,-1,-1);
		rep(i,n-1){
			cout<<ans[i]<<endl;
		}
	}
	return 0;
} 
	

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


int main(void)
{
  ll n;
	cin >> n;
  cout << n << ":";
  for(ll i = 2; i*i <= n; i++)
  {
      while(n % i == 0)
      {
        n /= i;
        cout << " " << i;
      }
    if (n == 1) break;
  }
  if (n != 1) cout << " " << n << endl;
  else cout << endl;
}


Measured memory_bytes: 3092
N = int(input())
c = list(input())

#cを[R,R,R,.....,R,W,W,W,.....,W]の形にする。

div = c.count('R')

c_for = c[:div]
c_lat = c[div:]

ans = 0

replace = min(c_for.count('W'), c_lat.count('R'))
change = max(c_for.count('W'), c_lat.count('R')) - replace

ans = replace + change
#実質 ans = max(c_for.count('W'), c_lat.count('R')) やんけ！

print(ans)

Measured memory_bytes: 12084
/*
  Contest 083
  B - Some Sums
  Rakesh Kumar --> 16/09/2020
 */

#include <bits/stdc++.h>

using ull = unsigned long long int;

inline int digits_sum(int n) {
    int sum = 0;
    for (char c : std::to_string(n))
        sum += c - '0';
    return sum;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0); std::cout.tie(0);

    int n = 0 , a = 0, b = 0;
    std::cin >> n >> a >> b;
    ull sum = 0;
    for (int i = 1; i <= n; ++i) {
        const int s = digits_sum(i);
        if (s >= a && s <= b)
            sum += i;
    }
    std::cout << sum << std::endl;

    return 0;
}


Measured memory_bytes: 3776
#include<stdio.h>
#include<stdlib.h>
int compara(const void *x, const void *y){
    int a = *((int *)x),b = *((int *)y);
    if(a<b)
        return -1;
    if(a>b)
        return 1;
}

int main(){
    int n,val=0;
    scanf("%d",&n);
    int vetor[n+1];
    for(int x=0;x<n;++x)
        scanf("%d",&vetor[x]);
    qsort(vetor,n,sizeof(vetor[0]),compara);
    for(;;){
        if(vetor[n/2]==vetor[(n/2)-1])
            break;
        else{
            val+=1;
            vetor[n/2]-=1;
        }
    }
    printf("%d\n",val);

    return 0;
}


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

using namespace std;

int main() {
    string s, t; cin >> s >> t;
    int n = s.size(), m = t.size();

    for (int i = n - m; i >= 0; i--) {
        bool ok = true;
        for (int j = 0; j < m; j++) {
            if (s[i + j] == '?') continue;
            if (s[i + j] != t[j]) {
                ok = false;
                break;
            }
        }

        if (!ok) continue;
        for (int j = 0; j < m; j++) s[i + j] = t[j];
        for (int i = 0; i < n; i++) if (s[i] == '?') s[i] = 'a';
        cout << s << endl;
        return 0;
    }

    cout << "UNRESTORABLE" << endl;
}


Measured memory_bytes: 3624
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

int main(void) {
	string S;
	cin >> S;
	int ans = 0;
	for (int i = 1; i < S.size(); i++) {
		if (S[i] == S[i - 1]) {
			if (S[i] == '1') S[i] = '0';
			else S[i] = '1';
			ans++;
		}
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 3848
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	tmp = input[0].split(" ");
	console.log(tmp[1]+tmp[0]);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29680
r,l = map(int,input().split())
if l-r+1 >= 2019:
    print("0")
    exit()
li = []
for i in range(l-r+1):
    li.append((r+i)%2019)
li.sort()
lia = []
for i in range(len(li)):
    for j in range(len(li)):
        if i != j:
            lia.append((li[i]*li[j])%2019)
print(min(lia))

Measured memory_bytes: 153792
#include <bits/stdc++.h>
using namespace std;
using ll= long long;
using vi= vector<int>;
using vvi= vector<vi>;
using vd= vector<double>;
using vvd= vector<vd>;
using vc= vector<char>;
using vb= vector<bool>;
#define rep(i,x,n) for(int i=x; i<n; i++)
#define all(x) x.begin(), x.end()


int main(){
  char c;
  cin >> c;

  printf("%c",c+1);
}


Measured memory_bytes: 256
#include<stdio.h>
	
int main(void){
	int mountains[100] = {0};
	int i,j,x;
	
	for(i=0; i<10; i++){
		scanf("%d",&x);
		mountains[i] = x;
		for(j=i; j>0; j-- ){
			if(mountains[j-1] < mountains[j]){
				x = mountains[j-1];
				mountains[j-1] = mountains[j];
				mountains[j] = x;
			}
		}
	}

	
	for(i=0; i<3; i++){
		printf("%d\n",mountains[i]);
	}
	
	return 0;
}

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

using namespace std;

#define INF (1 << 30)
#define INFL (1LL << 62)
#define MOD 1000000007
#define EPS 1e-10

using ll = long long;

int main() {
    string day[] = { "SUN", "MON", "TUE", "WED", "THU", "FRI", "SAT" };
    string s;
    cin >> s;
    cout << 7 - (find(day, day + 7, s) - day) << endl;

    return 0;
}

Measured memory_bytes: 256
n = gets.to_i
v = gets.split.map(&:to_i)

e = Hash.new(0)
o = Hash.new(0)

n.times do |i|
  if i.even?
    e[v[i]] += 1
  else
    o[v[i]] += 1
  end
end

e = e.sort_by { |_,v| -v }
o = o.sort_by { |_,v| -v }

e1 = e.shift
e2 = (e.shift || 0)
o1 = o.shift
o2 = (o.shift || 0)


if e1[0] == o1[0]
	puts n - [(e1[1] + o2[1]), (e2[1] + o1[1])].max
else
	puts n - (e1[1] + o1[1])
end

Measured memory_bytes: 20340
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

ll a, b, c, d, e;
bool v;
ll ans;

int main()
{
    scanf("%lld%lld%lld%lld%lld", &a, &b, &c, &d, &e);
    ans = a / 2 * 2 + d / 2 * 2 + e / 2 * 2;
    if(d > 0 && e > 0 && a > 0)
    {
        a--, d--, e--;
        ans = max(ans, a / 2 * 2 + d / 2 * 2 + e / 2 * 2 + 3);
    }
    printf("%lld\n", ans + b);
    return 0;
}


Measured memory_bytes: 256
K, N = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [0]*N
total = 0
max_val = A[1]-A[0]
for n in range(N-1):
  B[n] = A[n+1]-A[n]
  total += B[n]
  if max_val<B[n]:
    max_val = B[n]
B[N-1]=A[0]+K-A[N-1]
total += B[N-1]
if max_val<B[N-1]:
  max_val = B[N-1]
print(total-max_val)

Measured memory_bytes: 26444
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, m = MAP()

h = LIST()
dd = dict()
for _ in range(m):
    a, b = MAP()
    if(a in dd):
        dd[a].append(b)
    else:
        dd[a] = []
        dd[a].append(b)
    if(b in dd):
        dd[b].append(a)
    else:
        dd[b] = []
        dd[b].append(a)
ans = 0
for i in range(n):
    if((i+1) in dd):
        temp = dd[i+1]
        flag = 1
        for el in temp:
            if(h[el-1]>=h[i]):
                flag = 0
                break
        if(flag==1):
            ans+=1
    else:
        ans+=1
print(ans)

Measured memory_bytes: 99116
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,K=MAP()
S=input()

L=[]
cnt0=0
# 0始まりの時は番兵的に1の区間0を追加しておく
if S[0]=='0':
    L.append(0)
    cur=0
else:
    cur=1
cnt=0
# 1の区間の長さ、0の区間の長さ、1の区間の長さ...の配列Lを作る
for i in range(N):
    if cur==int(S[i]):
        cnt+=1
    else:
        L.append(cnt)
        if cur==0:
            cnt0+=1
        cnt=1
        # フラグの切り替え
        cur=1-cur
else:
    if cnt!=0:
        L.append(cnt)
        if cur==0:
            cnt0+=1
# 0終わりの時は番兵的に1の区間0を追加しておく
if S[-1]=='0':
    L.append(0)

acc=[0]+list(accumulate(L))
mx=0
if cnt0<K:
    # 0区間の数がKより少なかったら、それに合わせて区間和取る長さを短くする
    K=cnt0
for i in range(0, len(acc), 2):
    if i+(K*2+1)<len(acc):
        # 各区間和から最大を取る
        mx=max(mx, acc[i+(K*2+1)]-acc[i])
print(mx)


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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  int N; scanf("%d", &N);
  ll W; scanf("%lld", &W);

  vector<vector<ll>> items(4, vector<ll>());
  ll w0, w;
  ll v;
  scanf("%lld %lld", &w0, &v);
  items[0].push_back(v);
  for (int i = 1; i < N; ++i) {
    scanf("%lld %lld", &w, &v);
    items[w - w0].push_back(v);
  }
  for (int i = 0; i < 4; ++i) {
    sort(items[i].begin(), items[i].end(), greater<ll>());
    for (int j = 1; j < (int)items[i].size(); ++j) {
      items[i][j] += items[i][j - 1];
    }
  }

  ll ans = 0;
  for (int i = 0; i <= (int)items[0].size(); ++i) {
    ll a = i * w0;
    for (int j = 0; j <= (int)items[1].size(); ++j) {
      ll b = j * (w0 + 1);
      if (a + b > W) { break; }
      for (int k = 0; k <= (int)items[2].size(); ++k) {
        ll c = k * (w0 + 2);
        if (a + b + c > W) { break; }
        for (int l = 0; l <= (int)items[3].size(); ++l) {
          ll d = l * (w0 + 3);
          if (a + b + c + d > W) { break; }
          ll val = (i == 0) ? 0 : items[0][i - 1];
          val += (j == 0) ? 0 : items[1][j - 1];
          val += (k == 0) ? 0 : items[2][k - 1];
          val += (l == 0) ? 0 : items[3][l - 1];
          ans = max(ans, val);
        }
      }
    }
  }
  printf("%lld\n", ans);
  return 0;
}


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

int main() {
  int N, A; /* 支払金額Nと1円硬貨の枚数A */
  cin >> N >> A;
  // 500円硬貨無限枚数で支払い不可能な分の処理
  if (A >= N % 500) {
    cout << "Yes" << endl;
  }
  else {
  	cout << "No" << endl;
  }
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include <cmath>
#include <limits>
#include<set>
#include <iomanip>
#include <queue>
#include <map>
#include <string>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef double ld;
const long long INF=(1LL<<62);
const double inf=pow(10,10);
double pi=3.141592653589793;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
const ll MOD = 4000007;
void init(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
}

ll digit(ll n){
	string s=to_string(n);
	ll ret=0;
	for(int i=0;i<s.size();i++){
		ret+=(s[i]-'0');
		
	}
	return ret;
}


int main(){
	init();
	string s,t;cin>>s>>t;
	sort(s.begin(),s.end());
	sort(t.begin(),t.end(),greater<char>());
	
	if(s<t)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}


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

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

using ll = long long int;
const ll MOD = 1e9 + 7;

int main() {
  std::string S, T, U;
  int A, B;
  std::cin >> S >> T >> A >> B >> U;

  if(U == S) {
    --A;
  }
  if(U == T) {
    --B;
  }
  std::cout << A << " " << B << '\n';
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;
#define int long long

signed main(){
	int N;
	cin >> N;
	vector<int> A(N), B(N);
	bool f = true;
	for(int i = 0; i < N; ++i) {
		cin >> A[i] >> B[i];
		f = f && A[i] == B[i];
	}

	if(f) {
		cout << 0 << endl;
		return 0;
	}

	int sum = 0, mn = (int)1e10;
	for(int i = 0; i < N; ++i) {
		sum += A[i];
		if(A[i] > B[i]) {
			mn = min(mn, B[i]);
		}
	}
	cout << sum - mn << endl;

	return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
#include<complex>
using namespace std;
typedef long long int llint;
int main(){
	int x, y;
	cin >> x >> y;
	if (x == 2 || y == 2){
		cout << "No" << endl;
	}
	else if (x == 4 || x == 6 || x == 9 || x == 11){
		if (y == 4 || y == 6 || y == 9 || y == 11){
			cout << "Yes" << endl;
		}
		else{
			cout << "No" << endl;
		}
	}
	else if (y == 4 || y == 6 || y == 9 || y == 11){
		if (x == 4 || x == 6 || x == 9 || x == 11){
			cout << "Yes" << endl;
		}
		else{
			cout << "No" << endl;
		}
	}
	else{
		cout << "Yes" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
import bisect as bi
n = int(input())
l = list(map(int,input().split()))
l.sort()
#print(l)
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    ans += (bi.bisect_left(l,l[i]+l[j]))-j-1
    #print(i,j,bi.bisect_right(l,l[i]+l[j])-j-1)
    #print(ans)
print(ans)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
using lli = long long;
#define rep(i,n) for(int i=0;i<n;i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }


vector<lli> divisor(lli n){
    vector<lli> d;
    for(lli i = 1; i*i <= n; i++){
        if(n%i == 0){
            d.push_back(i);
            if(i != n/i) d.push_back(n/i);
        }
    }
    sort(d.begin(), d.end());
    return d;
}
lli n, m;

int main(void){
    cin >> n >> m;
    auto d = divisor(m);
    lli ans;
    rep(i, d.size()){
        if(d[i] >= n){
            ans = m/d[i];
            break;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3636
import java.util.*;

import static java.lang.System.*;

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

        PriorityQueue<Entry> pq = new PriorityQueue<Entry>(N, new EntryComparator());

        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            pq.add(new Entry(sc.nextLong(), sc.nextInt()));
        }

        long price = 0;
        int count = 0;
        while(!pq.isEmpty()){
            Entry entry = pq.poll();
            int tmpCount = entry.E;
            long tmpPrice = entry.S;

            if(tmpCount + count < M){
                price += tmpCount * tmpPrice;
                count += tmpCount;
            } else {
                price += (M - count) * tmpPrice;
                break;
            }
        }

        out.println(price);
    }

    // 小さい順番に並べる
    static class EntryComparator implements Comparator<Entry> {
        @Override
        public int compare(Entry t1, Entry t2) {
            if (t1.S > t2.S) {
                return 1;
            }
            return -1;
        }
    }

    static class Entry {
        public long S;
        public int E;

        public Entry(long S, int E){
            this.S = S;
            this.E = E;
        }
    }
}


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

int main(void){
    int n,m,X,Y;
    cin>>n>>m>>X>>Y;
    int maxX = -100, minY = 100;
    rep(i,n){
        int x;
        cin>>x;
        maxX = max(maxX, x);
    }
    rep(i,m){
        int y;
        cin>>y;
        minY = min(minY, y);
    }
    cout<<((max(X,maxX)<min(Y,minY)) ? "No War" : "War")<<endl;
    return 0;
}


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

  ll n;
  cin >> n;
  ll ans_i=1,ans_j=1;
  ll ans;


  for(ll i=1;i<=sqrt(n);i++){
    if(n%i==0)ans=i;
  }

  cout << n/ans+ans-2 << endl;


  
  return 0;
}

Measured memory_bytes: 256
s = input()
k = int(input())
n = len(s)
for i in range(n):
  num = ord(s[i])
  if num == 97 or 123-num > k:
    continue
  k -= (123-num)
  s = s[:i] + 'a' + s[i+1:]
if k > 0:
  t = k%26
  s = s[:n-1] + chr(ord(s[n-1])+t)
print(s)  


Measured memory_bytes: 3460