akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
  public static void main (String[] args) {
    Scanner sc = new Scanner(System.in);
    
    int n = sc.nextInt();
    int a[] = new int[n];
    for (int i = 0; i < n; i++) a[i] = sc.nextInt();
    
    int y = 0;
    while (true) {
      int x = 0;
      for (int i = 0; i < n; i++) {
        if (a[i] % 2 == 0) {
          a[i] /= 2;
          x++;
        } else {
          break;
        }
      }
      if (x == n) {
        y++;
      } else {
        break;
      }
    }
    
    System.out.println(y);
 }
}

Measured memory_bytes: 21844
N,A,B=map(int,input().split())
E = 0
def ans(N):
  K = str(N)
  T = list(map(int,K))
  return (sum(T)) 
  
S = list(range(N+1))
for i in S:
  num = ans(S[i])
  if num >= A and num <= B:
    E += S[i]
print(E)

Measured memory_bytes: 3444
N,K,*A = `dd`.split.map &:to_i
if K == 1
  p 0; exit
end
A.map!{ |a| (a - 1) % K }
ring = [0]
ch = { 0 => 1 }
s = 0
n = 0
A.each_with_index{ |a,i|
  s = (s + a) % K
  n += (ch[s] || 0)
  ch[s] = (ch[s] || 0) + 1
  ring << s
  if ring.size >= K
    t = ring[-K]
    if t && ch[t]
      ch[t] = ch[t] - 1
    end
  end
}
p n

Measured memory_bytes: 32396
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int n;
int a,b,col[100007],vis[100007],mark[100007],cnt=-1,cur=0,k1=0,k2=0;
vector <int> edge[100007];
void dfs(int u){
    vis[u]=1;
    for(int i=0;i<(int)edge[u].size();i++){
        int v=edge[u][i];
        if(vis[v]==1) continue;
        dfs(v);
        if(mark[v]==1) mark[u]=1,cnt++;
    }
}
void start(int u){
    if(cur<=(cnt+1)/2) col[u]=1;
    else col[u]=2;
    vis[u]=1;
    cur++;
    for(int i=0;i<(int)edge[u].size();i++){
        int v=edge[u][i];
        if(vis[v]==1) continue;
        if(mark[v]==1){
            start(v);
            break;
        }
    }
}
void sol(int u){
    vis[u]=1;
    if(col[u]==1) k1++;
    else k2++;
    for(int i=0;i<(int)edge[u].size();i++){
        int v=edge[u][i];
        if(vis[v]==1) continue;
        if(col[v]==0 || col[v]==col[u]){
            col[v]=col[u];
        }
        sol(v);
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>a>>b;
        edge[a].pb(b);
        edge[b].pb(a);
    }
    mark[n]=1;
    dfs(1);
    memset(vis,0,sizeof(vis));
    start(1);
    memset(vis,0,sizeof(vis));
    sol(1);
    //cout<<k1<<" "<<k2<<endl;
    if(k1>k2) cout<<"Fennec";
    else if(k2>=k1) cout<<"Snuke";
}


Measured memory_bytes: 13184
def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    b = sorted(a, reverse=True)
    for i in range(n):
        if b[0] !=  a[i]:
            print(b[0])
        else:
            print(b[1])
   
    
if __name__ == '__main__':
    main()

Measured memory_bytes: 14112
import java.util.Scanner;

public class Main {
	public static void main(String args[]){
		Scanner scan = new Scanner(System.in); 
		int x, y;
		
		for(int i = 1; i <= 10000; i++){
			x = scan.nextInt();
			y = scan.nextInt();
			
			if(x == 0 && y == 0){
				break;
			}
			
			if(x > y){
				int a;
				a = x;
				x = y;
				y = a;
			}
			
			System.out.println(x + " " + y);
		}
	
	}

}

Measured memory_bytes: 35452
n,m,x=[int(i) for i in input().split()]
a = [int(i) for i in input().split()]

sum_0 = 0
sum_N = 0

for i in range(len(a)):
    if a[i]<x:
        sum_0 +=1
    if a[i]>x:
        sum_N+=1
print(min(sum_0, sum_N))


Measured memory_bytes: 3060
import Data.Bool
import Data.List
import Data.Bits
main=interact$show.solve.map(map read.words).lines
solve[[n],as,bs]=(\m->if m==inf then -1 else m).foldr f inf$ds where
  ds=filter(\d->popCount d==n`div`2)[0..shift 1 n-1::Int]
  f d m=if or.(zipWith(<)=<<tail)$map fst r then m else min m c where
    c=sum$zipWith(\j i->length$filter(>i)$take j is)[0..]is where is=map snd r
    r=(\(e,o)->h(sort e)(sort o)).foldr(g d)([],[]).zip[0..n-1]$zip as bs
g d(i,(a,b))(e,o)=if testBit d i then(e,v:o)else(v:e,o)where
  v=(bool b a$testBit d i==(i.&.1/=0),i)
h(a:as)bs=a:h bs as
h _ _=[]
inf=maxBound::Int

Measured memory_bytes: 52872
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

typedef long long ll;

const int MAX = 200010;
int n;
int R[MAX];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &R[i]);
    }
    int mi = R[0];
    int ans = -2000000000;
    for (int i = 1; i < n; i++) {
        ans = max(ans, R[i] - mi);
        mi = min(mi, R[i]);
    }
    printf("%d\n", ans);
    return 0;
}

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

int main() {
     int h,w,n,a[10010]; int ans[105][105];
     cin>>h>>w>>n; for(int i=0;i<n;i++)cin>>a[i];
     bool flag=true; int num=0;
     for(int i=0;i<h;i++)
     {
     	for(int j=0;j<w&&flag;j++){if(!a[num])num++; ans[i][j]=num+1; a[num]--;}
     	for(int j=w-1;!flag&&j>=0;j--){if(!a[num])num++; ans[i][j]=num+1; a[num]--;}
     	flag^=1;
     }
     for(int i=0;i<h;i++){for(int j=0;j<w;j++)cout<<ans[i][j]<<" "; cout<<endl;}
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int main(){
  int64_t h,w;
  cin>>h>>w;
  int64_t m;
  for(int i=1;i<=h-i;i++){
    int64_t a,b,c,d;
    a=i*w;
    if((h-i)*w%2==0)
      b=(h-i)*w/2;
    else
      b=max(h-i,w)/2*min(h-i,w);
    c=(h-i)*w-b;
    d=max({a,b,c})-min({a,b,c});
    m=(i==1?d:min(m,d));
  }
  for(int i=1;i<=w-i;i++){
    int64_t a,b,c,d;
    a=i*h;
    if((w-i)*h%2==0)
      b=(w-i)*h/2;
    else
      b=max(w-i,h)/2*min(w-i,h);
    c=(w-i)*h-b;
    d=max({a,b,c})-min({a,b,c});
    m=min(m,d);
  }
  cout<<m<<endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
static const int INF = 2000000000;

int main(){
  int n;
  cin >> n;
  vector<int> d(3);
  rep(i, 3) cin >> d[i];
  vector<P> q;
  rep(i, n){
    string s;
    cin >> s;
    int a = 0, b = 1;
    if (s == "AB") a = 0, b = 1;
    if (s == "AC") a = 0, b = 2;
    if (s == "BC") a = 1, b = 2;
    q.emplace_back(a, b);
  }
  q.emplace_back(0, 1);
  string ans;
  auto add = [&](int a, int b){
    d[a]++;
    d[b]--;
    ans += 'A' + a;
  };
  rep(i, n){
    int a = q[i].first;
    int b = q[i].second;
    if (!d[a] && !d[b]) {
      cout << "No\n";
      return 0;
    }
    if (!d[a]) add(a, b);
    else if (!d[b]) add(b, a);
    else {
      int na = q[i+1].first;
      int nb = q[i+1].second;
      if (a == na || a == nb) add(a, b);
      else add(b, a);
    }
  }
  cout << "Yes\n";
  rep(i, n) cout << ans[i] << endl;
}


Measured memory_bytes: 4320
#include <cstdio>
#include <queue>
#define N 200005
using namespace std;

int n , s[N] , t[N];
typedef pair<int , int> pa;

priority_queue<pa> q;

int prev(int x){return x == 1 ? n : x - 1;}
int next(int x){return x == n ? 1 : x + 1;}
long long ans;
int main()
{
	scanf("%d" , &n);
	for(int i = 1 ; i <= n ; i ++) 
		scanf("%d" , t + i);
	for(int i = 1 ; i <= n ; i ++)
		scanf("%d" , s + i) , q.push( make_pair(s[i] , i) );
	while(!q.empty())
	{
		int val = q.top().first , id = q.top().second;
		q.pop();
		if(t[id] == val)  continue;
		int around = s[prev(id)] + s[next(id)];
		int cnt = (val - t[id]) / around;
		if(cnt <= 0) return puts("-1") & 0;
		ans += cnt; s[id] = val - cnt * around;
		q.push( make_pair(s[id] , id) );
	}
	return printf("%lld\n" , ans) & 0;
}

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


int main(){
        int ans = 0;
        int n, p, m;
        cin >> n;
        for (int i = 0; i < n; ++i){
                cin >> p;
                if(i==0){
                        m = p;
                }
                if(min(m,p)==p){
                        ans += 1;
                        m = p;
                }
        }
        cout << ans << endl;
}

Measured memory_bytes: 256
# seishin.py
K, N = map(int, input().split())
if K % 2 == 0:
    print(*[K//2] + [K]*(N-1))
else:
    X = [(K+1)//2] * N
    for i in range(N//2):
        if X[-1] == 1:
            X.pop()
        else:
            X[-1] -= 1
            X.extend([K]*(N-len(X)))
    print(*X)


Measured memory_bytes: 12348
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()

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

    int N, M;
    cin >> N >> M;
    vector<int> cnt(N+1);
    REP(i, M) {
        int a, b;
        cin >> a >> b;
        cnt[a]++;
        cnt[b]++;
    }
    for (int i = 1; i <= N; i++) {
        if (cnt[i] % 2 == 1) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
}

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

int main(){
    int N;
    cin >> N;
    map<string, int> dic;
    for(int i = 0; i < N; i++){
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        dic[s] = dic[s] + 1;
    }
    ll ans = 0;
    ll tmp = 0;
    for(auto itr = dic.begin(); itr != dic.end(); ++itr){
        tmp = itr->second;
        if(tmp == 1) continue;

        ans = ans + ( tmp * (tmp - 1) / 2);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 11136
//s.empty() //emptyなら1を出力 入っていれば0を出力
/*//ABC018-B 部分的にreverseをかける解法
int main() {
  string s;
  cin >> s;
  int n;
  cin >> n;
  vector<int>a(n);
  vector<int>b(n);
  rep(i,n) cin>>a.at(i)>>b.at(i);
  rep(i,n)a.at(i)--;
  rep(i,n)b.at(i)--;
  string t;
  rep(i,n){
    t = s;
    for(int k=0;k<=b.at(i)-a.at(i);k++){
      t.at(a.at(i)+k) = s.at(b.at(i)-k);
    }
    s = t;
  }
  cout << s << endl;
}
*///ABC018-B
//  string s;
//  cin >> s;
//  cout << s.at(0) <<endl;
//  cout << s.at(0)-'0' <<endl;
//  Aが16？
//  cout << char(i+48) << endl;//なぜかaは47と得る時がある。+48で出力もaにできる。
//  cout << char(97) << endl;//アスキーコードでaを出力
// sort(b.begin(), b.end());//bという配列を小さい方からソート
// reverse(b.begin(), b.end());//bという配列をリターン
// 10桁でdouble出力するパターン１ 
// printf("%.10f\n", ma);
// 10桁でdouble出力するパターン２
//cout << fixed << setprecision(10);
//  cout << ma << endl;

/*01 02 03 12 13 23　と６回見ていくパターン 
for(int i=0;i<n-1;i++){
  for(int j=i+1;j<n;j++){
    }
  }
*///vector<vector<int>> data(3, vector<int>(4));//int型の2次元配列(3×4要素の)の宣言
//int64_t a;
//10のi乗pow(10, i);
/*string s; stringでの文字列を数字型に変える方法
  cin >> s;
  rep(i,s.size()-2) {
  int a= (s.at(i)-'0')*100 + (s.at(i+1)-'0')*10+ s.at(i+2) -'0';
    */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
  string s,t;
  cin >> s >> t;
  int count = 0;
  for(int i=0;i<s.size();i++){
    if(s.at(i)!=t.at(i))count++;
  }
  cout<< count << endl;
}


Measured memory_bytes: 3864
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <utility>
#include <climits>
#include <iomanip>
using namespace std;
#define MAXSIZE 100005
#define MAXL 100
#define MOD_CONST 1000000007
typedef long long int lli;

vector<int> input_vector(const int &num){
    vector<int> res(num);
    for(int i = 0; i < num; ++i){
        cin >> res[i];
    }
    return res;
}

int get_ans(int &point, const int &x, const vector<int> &l_vec){
    int cnt = 1;
    for(int i : l_vec){
        point += i;
        if(point <= x){
            cnt++;
        }
    }
    return cnt;
}

int main(){
    int n, x;
    cin >> n >> x;
    vector<int> l_vec = input_vector(n);

    int point = 0;
    int ans = get_ans(point, x, l_vec);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<ctype.h>

int main(void){
    int K,answer = 0;
    scanf("%d",&K);

    for(int i=2; i<=K; i+=2){
        for(int j=1; j<=K; j+=2){
            answer++;
        }
    }

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


Measured memory_bytes: 128
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


def solve():
    _ = int(rl())
    X = list(map(int, rl().rstrip()))[::-1]
    
    ones = X.count(1)
    upmod = X[0] % (ones + 1)
    c = 1
    for xi in X[1:]:
        c = c * 2 % (ones + 1)
        upmod = (upmod + c * xi) % (ones + 1)
    botmod = 0
    if ones - 1 != 0:
        botmod = X[0] % (ones - 1)
        c = 1
        for xi in X[1:]:
            c = c * 2 % (ones - 1)
            botmod = (botmod + c * xi) % (ones - 1)
    
    ans = []
    for i, xi in enumerate(X):
        if ones == 1 and xi == 1:
            ans.append(0)
            continue
        if xi == 0:
            xmod = (upmod + pow(2, i, ones + 1)) % (ones + 1)
        else:
            xmod = (botmod - pow(2, i, ones - 1)) % (ones - 1)
        cnt = 1
        while xmod != 0:
            xmod = xmod % popcount(xmod)
            cnt += 1
        ans.append(cnt)
    print(*ans[::-1], sep='\n')


if __name__ == '__main__':
    solve()


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

bool odd(char s){
  vector<char> ok_list{'R','U','D'};
  for(int i=0;i<3;++i){
    if(ok_list[i]==s) return true;
  }
  return false;
}

bool even(char s){
  vector<char> ok_list{'L','U','D'};
  for(int i=0;i<3;++i){
    if(ok_list[i]==s) return true;
  }
  return false;
}

int main(){

  string S;
  cin >> S;
  bool flg = true;
  for(int i=0;i<S.length();++i){
    if((i+1)%2 == 0){
      if (!even(S[i])){
        flg = false;
        break;
      }
    } else {
      if (!odd(S[i])){
        flg = false;
        break;
      }
    }
  }
  if (flg) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_D main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 10;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions
struct DSU {
    int N;
    vi dt;
    DSU(int n) : N(n), dt(n, -1) {}

    int root(int v){
        if (dt[v] < 0) return v;
        return dt[v] = root(dt[v]);
    }

    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (size(x) < size(y)) swap(x,y);
        dt[x] += dt[y];
        dt[y] = x;
        return true;
    }

    int size(int v) {return -dt[root(v)];}
};
#endif 


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

    ll N, M; cin >> N >> M;
    vi A(M), B(M);
    REP(i,M) {
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }

    DSU du(N);
    vl ans(M);
    ans[M-1] = (N-1) * (1 + (N-1)) / 2;
    for (int i = M - 1; i >= 1; i--) {
        ans[i - 1] = ans[i];
        if (du.root(A[i]) != du.root(B[i])) {
            ans[i - 1] -= ((ll)du.size(A[i]))*du.size(B[i]);
            du.unite(A[i], B[i]);
        }
    }

    REP(i,M) cout << ans[i] << endl;

    return 0;
}

Measured memory_bytes: 3328
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <string>
#include <vector>

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

using namespace std;
using ll = long long;
using P = pair<int, int>;

template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& v) {
    os << "(" << v.first << ", " << v.second << ")";
    return os;
}
 
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    rep(i, v.size()) {
        if (i) os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

int main()
{
    int h, w, k;
    cin >> h >> w >> k;
    bool s[10][1000];
    rep(i, h) {
        rep(j, w) {
            char c; cin >> c;
            s[i][j] = c == '1';
        }
    }

    int min_cut = h + w;
    for (int check = 0; check < (1 << (h - 1)); check++) {
        vector<pair<int, int>> range;
        int last = 0;
        for (int i = 1; i < h; i++) {
            if ((check >> (i - 1)) & 1) {
                if (last < i) {
                    range.emplace_back(last, i);
                    last = i;
                }
            }
        }

        range.emplace_back(last, h);
        // cout << range << endl;

        int h_cut_count = range.size() - 1;
        int w_cut_count = 0;
        int j = 0;
        while (j < w) {
            int old_j = j;
            vector<int> cnt(range.size(), 0);

            while (j < w) {
                for (int c = 0; c < (int)range.size(); c++) {
                    for (int i = range[c].first; i < range[c].second; i++) {
                        if (s[i][j]) cnt[c]++;
                    }
                }
                // cout << j << " " << cnt << endl;
                bool flag = false;
                for (auto c : cnt) {
                    if (c > k) {
                        flag = true;
                        break;
                    }
                }
                if (flag) {
                    w_cut_count++;
                    break;
                }
                j++;
            }
            if (j == old_j) {
                w_cut_count = 10e8;
                break;
            }
        }
        if (min_cut > w_cut_count + h_cut_count)
            min_cut = w_cut_count + h_cut_count;
    }
    cout << min_cut << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <string>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <iomanip>
#include <queue>
#include <functional>
#include <iso646.h>
#include <bitset>

#ifndef M_PI
#define M_PI 3.14159265358979
#endif
#define deg_to_rad(deg) (((deg) / 360) * 2 * M_PI)
#define rad_to_deg(rad) (((rad) / 2 / M_PI) * 360)

using namespace std;

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

const ll INF = 1e15;
const ll MOD = 1e9 + 7;

const ll MAX_N = 1e5;

ll par[MAX_N];
ll u_rank[MAX_N];

void init(ll n)
{
	for (ll i = 0; i < n; i++)
	{
		par[i] = i;
		u_rank[i] = 0;
	}
}

ll find(ll x)
{
	if (par[x] == x)
	{
		return x;
	}
	else
	{
		return par[x] = find(par[x]);
	}
}

void unite(ll x, ll y)
{
	x = find(x);
	y = find(y);
	if (x == y)
		return;
	if (u_rank[x] < u_rank[y])
	{
		par[x] = y;
	}
	else
	{
		par[y] = x;
		if (u_rank[x] == u_rank[y])
			u_rank[x]++;
	}
}

bool same(ll x, ll y)
{
	return find(x) == find(y);
}

int main()
{
	ll N, M;
	ll i, j;

	cin >> N >> M;
	vll H;
	for (i = 0; i < N; i++)
	{
		ll h;
		cin >> h;
		H.push_back(h);
	}
	vector<vll> T(N);
	for (i = 0; i < M; i++)
	{
		ll a, b;
		cin >> a >> b;
		T[a - 1].push_back(b - 1);
		T[b - 1].push_back(a - 1);
	}
	ll ans = 0;
	for (i = 0; i < N; i++)
	{
		bool ok = true;
		for (j = 0; j < T[i].size(); j++)
		{
			if (H[i] <= H[T[i][j]])
			{
				ok = false;
				break;
			}
		}
		if (ok)
		{
			ans++;
		}
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 9380
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

def check(cir,num):
    m = len(cir)
    a = sum(cir)
    if num == 0:
        ss = 0
    elif num == 1:
        ss = max(cir)
    else:
        ac = list(accumulate([0]+cir))
        l = 0
        r = 1
        ss = ac[r]-ac[l]
        i = 0
        while 1:
            if r == m:
                l = ac[l+1:r].index(min(ac[l+1:r])) + l+1
                ss = max(ss,ac[r]-ac[l])
                break
            elif i%2==0:
                r = ac[r+1:l+num+1].index(max(ac[r+1:l+num+1])) + r+1
            else:
                l = ac[l+1:r].index(min(ac[l+1:r])) + l+1
            i+=1
            ss = max(ss,ac[r]-ac[l])

        num = m-num
        l = 0
        r = num
        i = 0
        ss = max(ss,a-ac[r]+ac[l])
        while 1:
            if r == m:
                l = ac[l+1:r-num+1].index(max(ac[l+1:r-num+1])) + l+1
                ss = max(ss,a-ac[r]+ac[l])
                break
            elif i%2==0:
                r = ac[r+1:l+m].index(min(ac[r+1:l+m])) + r+1
            else:
                l = ac[l+1:r-num+1].index(max(ac[l+1:r-num+1])) + l+1
            i+=1
            ss = max(ss,a-ac[r]+ac[l])
    return ss


from itertools import accumulate

n,k = readints()
p = [x-1 for x in readints()]
c = readints()

circles = []
used = [0]*n

for i in range(n):
    if not used[i]:
        circles.append([c[i]])
        used[i] = 1
        j = p[i]
        while not used[j]:
            circles[-1].append(c[j])
            used[j] = 1
            j = p[j]

score = -10**20

for cir in circles:
    m = len(cir)
    a = sum(cir)
    if k>m:
        if a>0:
            score = max(score, (k//m)*a + check(cir,k%m), (k//m-1)*a + check(cir,m))
        else:
            score = max(score,check(cir,m))
    else:
        score = max(score,check(cir,k))

print(score)










Measured memory_bytes: 10160
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define len(x) (int)(x.size())
#define all(vs) vs.begin(), vs.end()
using ii = pair<int, int>;
using ll = long long;
#define MAXN 200000100


int32_t main(){
	ios::sync_with_stdio(0);
	int n;
	cin >> n;
	vector<int> vs(n);
	for(auto &x:vs) cin >> x;
	int k = 0;
	for(auto x:vs)
		if(x==k+1) ++k;
	int ans = len(vs)-k;
	if(k==0) ans = -1;
	cout << ans << endl;
}



Measured memory_bytes: 1792
#include <stdio.h>

int n;
long long int t[1001], a[1001];

int main(void) {
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%lld %lld", t+i, a+i);

    for(int i=1; i<n; i++) {
        long long int df=1;
        
        if(t[i] >= t[i-1] && a[i] < a[i-1])
            df =(a[i-1]-1) / a[i] + 1;
        
        if(a[i] >= a[i-1] && t[i] < t[i-1])
            df = (t[i-1]-1) / t[i] + 1;
        
        if(t[i] < t[i-1] && a[i] < a[i-1])
        {
            long long int dt = (t[i-1]-1) / t[i] + 1;
            long long int da = (a[i-1]-1) / a[i] + 1;
            df = dt > da ? dt : da;
        }
        
        t[i] = t[i] * df;
        a[i] = a[i] * df;
    }

    printf("%lld", t[n-1] + a[n-1]);
    
    return 0;
}

Measured memory_bytes: 128
if __name__ == "__main__":
    n,m,k = (int(x) for x in input().split())
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]

    pre = 0
    for i in range(len(a)):
        pre += a[i]
        a[i] = pre
    
    pre = 0
    for i in range(len(b)):
        pre += b[i]
        b[i] = pre

    ans = 0
    for i in range(-1,len(a)):
        have = k
        if i >= 0:
            have -= a[i]
        if have <0:
            continue
        ans = max(ans, i+1)
        if b[0] > have:
            continue
        low, high = (0, len(b)-1)
        while low<=high:
            mid = (low+high)//2
            if have >= b[mid]:
                low = mid + 1
            else:
                high = mid - 1
        ans = max(ans, i+1 + high+1)
    print(ans)

        
        

Measured memory_bytes: 40492
#include <stdio.h>

int main()
{
  int i,j,key,n,m;
  int l[100];

  scanf("%d",&n);/* 要素の数の格納 */

  for(i=0;i<n;i++){
    scanf("%d",&l[i]);/* 配列の格納 */
  }
  for(i=0;i<n;i++){
    printf("%d",l[i]);/* 変換前の配列の表示 */
    if(i<n-1)printf(" ");/* 空白の表示 */
  }
  printf("\n");/* 改行の表示 */

  for(i=1;i<n;i++){
    key = l[i];/* 位置の変換のために後続の値を入れる変数 */
    j = i - 1;
    while(l[j]>key && j>=0){/* 位置の変換の条件 */
      l[j+1] = l[j];/* 位置の変換 */
      j--;
    }
    l[j+1] = key;/* 位置の変換 */
    for(m=0;m<n;m++){
      printf("%d",l[m]);/* 変換後の配列の表示 */
      if(m<n-1)printf(" ");/* 空白の表示 */
    }
  printf("\n");/* 改行の表示 */
  } 
   return 0;
}




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



int main() {
    int N;
    cin>>N;
    N%=1000;
    N=1000-N;
    if(N==1000)N=0;
    cout<<N<<endl;
}

Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
int n,ans,a[100005],d[100005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i]; 
	int ans=1;d[1]=a[n];
	for(int i=n-1;i>=1;i--){
		int k=upper_bound(d+1,d+1+ans,a[i])-d;
		if(k>ans) d[++ans]=a[i];
		if(d[k]>a[i]) d[k]=a[i];
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <sstream>
#include <queue> 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> 
#include <numeric>  
#include <functional>
#include <cassert>
#include <bitset>
#include <cctype>  
#include <iomanip> 
#include <limits>  
#include <regex>
// std::numeric_limits<int>::max(), min()
// std::setprecision(X)
// std::islower(), std::isupper(), std::tolower, std::toupper
// std::accumulate(m.begin(), m.end(), 0LL);
// std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
// std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
// if ( std::regex_match(S, std::regex("(dream|dreamer|erase|eraser)*")) ) std::cout << "YES" << std::endl;

#define rep(i,n)  for(int i = 0; i < (int)(n);    i++)
#define sz(x)     ((int)(x).size())
#define all(x)    (x).begin(),(x).end()

using ll = long long;

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

int main (void) {
  std::cin.tie(0);  std::ios::sync_with_stdio(false);
  int n; std::cin >> n;
  std::vector<int> a(n); rep(i,n) std::cin >> a[i];

  int cnt = 0;
  rep(i,n) {
    if ( i % 2 == 0 && a[i] % 2 == 1 ) cnt++;
  }
  std::cout << cnt << std::endl;
  return 0;
}



Measured memory_bytes: 3612
open Batteries
open Tuple
module EnumL = Enum.Labels
module ListL = List.Labels
module ArrayL = Array.Labels

let dbg0 x = Printf.eprintf "[debug]%s\n" @@ dump x
let dbg1 x = dbg0 x; x

let id = identity

let (++) n m = List.range n `To m
let (++^) n m = if n < m then List.range n `To (pred m) else []

let scan fmt = Scanf.sscanf (read_line ()) fmt

let scan_lines n fmt f =
  if n = 0 then []
  else List.map (fun _ -> scan fmt f) (1 ++ n)

let scan_list sep cnv =
  let line = read_line () in
  (match sep with
   | None -> List.map String.of_char @@ String.to_list line
   | Some sep -> String.split_on_char sep line)
  |> List.map cnv

let scan_array ?sep cnv = Array.of_list @@ scan_list sep cnv

let scan_matrix n m e ?sep conv =
  let arr = Array.make_matrix n m e in
  ListL.iter (0 ++^ n)
    ~f:(fun i -> arr.(i) <- Array.of_list @@ scan_list sep conv);
  arr

let rec powerset e =
  match Enum.get e with
  | None -> Enum.singleton @@ Enum.empty ()
  | Some v ->
    let f = powerset e in
    let g = Enum.clone f in
    EnumL.map f ~f:(fun x -> let y = Enum.clone x in push y v; y)
    |>  Enum.append g

let permutations l =
  let rec aux l =
    let rec interleave x = function
      | [] -> [[x]]
      | (hd::tl) as lst ->
        (x::lst) ::
        (ListL.map ~f:(List.cons hd)  @@ interleave x tl)
    in
    match l with
    | [] -> [[]]
    | hd::tl -> List.concat @@ List.map (interleave hd) @@ aux tl in
  let l = List.sort (List.compare Int.compare) @@ aux @@ List.of_enum l in
  List.enum % ListL.map ~f:List.enum @@ l

let intersection l =
  EnumL.filter ~f:(fun x -> EnumL.exists ~f:((=) x) @@ Enum.clone l)

let lower_bound n f =
  let rec aux l u =
    if u - l > 1 then
      let m = (l + u) / 2 in
      if f m then aux l m
      else aux m u
    else u in aux (-1) n

let between n x m = n <= x && x < m

let (n,k) = scan "%d %d" Tuple2.make
let arr = scan_array ~sep:' ' Int.of_string

let memo = Array.make_matrix (succ k) 2 None

let rec solve k t =
  match memo.(k).(if t then 1 else 0) with
  | Some v -> v
  | None ->
    let v = if t then
        if k < arr.(0) then 0
        else if ArrayL.exists arr ~f:(fun a ->
            if k - a >= 0 then solve (k-a) false = 1 else false) then 1
        else 0
      else
      if k < arr.(0) then 1
      else if ArrayL.exists arr ~f:(fun a ->
          if k - a >= 0 then solve (k-a) true = 0 else false) then 0
      else 1 in
    memo.(k).(if t then 1 else 0) <- Some v; v

let () =
  solve k true
  |> (fun b -> Printf.printf "%s\n" (if b = 1 then "First" else "Second"))


Measured memory_bytes: 26624
w,h,n = map(int,input().split())
pos_list = [map(int,input().split()) for _ in range(n)]
s = [0,0]
f = [w,h]
for x,y,a in pos_list:
    if a == 1:
        s[0] = max(s[0],x)
    elif a == 2:
        f[0] = min(f[0],x)
    elif a == 3:
        s[1] = max(s[1],y)
    elif a == 4:
        f[1] = min(f[1],y)

if f[0]-s[0] <= 0 or f[1] - s[1] <= 0:
    print(0)
else:
    print((f[0]-s[0])*(f[1]-s[1]))

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

using namespace std;

template <typename T>
T gcd(T a, T b) {
  return (b ? gcd(b, a % b) : a);
}

template <typename T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}

int main() {
  int64_t A, B;
  cin >> A >> B;
  cout << lcm(A, B) << 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;
using P = pair<int, int>;
typedef long long ll;

//約数列挙 計算量O(sqrt(n))
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}

int main() {
  ll n;
  cin >> n;
  map<ll, ll> mp;
  vector<ll> ans1 = divisor(n - 1);
  vector<ll> ans2 = divisor(n);
  for (int i = 1; i < ans1.size(); i++){
    mp[ans1[i]]++;
  }
  mp[n]++;
  for (int i = 1; i < ans2.size(); i++){
    ll num = n;
    while(num % ans2[i] == 0){
      num /= ans2[i];
    }
    if(num % ans2[i] == 1) mp[ans2[i]]++;
  }
  cout << mp.size() << endl;
}

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

using namespace std;

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

    int a, b;
    cin >> a >> b;

    if(a % 2 == 0 || b % 2 == 0)
        cout << "No";
    else
        cout << "Yes";

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		String str = sc.next();
		int acnt = 0;
		int bcnt = 0;
		int ccnt = 0;

		for (int i = 0; i < 3; i++) {
			if (str.substring(i, i + 1).equals("a")) {
				acnt++;
			}
			if (str.substring(i, i + 1).equals("b")) {
				bcnt++;
			}
			if (str.substring(i, i + 1).equals("c")) {
				ccnt++;
			}
		}
		if (acnt == 1 && bcnt == 1 && ccnt == 1) {
			System.out.println("Yes");

		} else {
			System.out.println("No");
		}
	}

}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i = (int)(j);i <= (int)(k);i ++)
#define debug(x) cerr<<#x<<":"<<x<<endl
#define fix cout<<fixed<<setprecision(20);
const int maxn=(int)1e6+5;
typedef long long ll;
ll MOD = (ll)1e9+7;
inline ll qpow(ll a, ll b) {return b? ((b&1)? a*qpow(a*a%MOD,b>>1)%MOD: qpow(a*a%MOD,b>>1))%MOD: 1;}
inline ll gcd(ll a, ll b) {return b? gcd(b, a%b): a;}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll n;cin>>n;
    vector<ll> c(n);
    rep(i,1,n)cin>>c[i-1];
    sort(c.begin(),c.end(),greater<ll> ());
    ll ans=0;
    rep(i,0,n-1)ans+=c[i]*(i+2)%MOD,ans%=MOD;
    //debug(ans);
    ans*=qpow(4,n-1);
    ans%=MOD;
    cout<<ans<<endl;
}
/* 
组合数学题。
2^N 个二进制串，转化的花费是 按照C_i递减乘不同位数
求所有对花费之和
1.By the observations above and symmetry, we assume that C is monotonically non-increasing.
2.Decompose the contributions of sums, and consider how many times Ci are added.
 */

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<char> s(n);
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    
    for(int i=0;i<n;i++){
        if('Y'==s[i]){
            cout<<"Four"<<endl;
            return 0;
        }
    }
    cout<<"Three"<<endl;
    return 0;
}


Measured memory_bytes: 256
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main() {

	LL n; cin >> n;
	vector<LL> a(5);

	for (int i = 0; i < 5; i++) {
		cin >> a[i];
	}

	LL mi = *min_element(a.begin(), a.end());

	LL cnt = (n + mi - 1) / mi;
	LL ans = 4 + cnt;

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <tuple>
#include <cstring>
#include <map>
#include <iomanip>
#include <ctime>
#include <complex>
#include <cassert>
#include <climits>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _ << " " <<
#define all(X) (X).begin(), (X).end()
#define len(X) (X).size()
#define Pii pair<int, int>
#define Pll pair<ll, ll>
#define Tiii tuple<int, int, int>
#define Tlll tuple<ll, ll, ll>

int main() {
    ll n, k, mod = 1e9 + 7;
    cin >> n >> k;
    k--;
    int kc = k;

    if (n*n <= 1e9) {
        vector<ll> a(n + 1, 1);
        while (k--) {
            vector<ll> s(n + 1, 0);
            for (int i = 1; i <= n; i++) {
                s[i] = a[i] + s[i - 1];
                s[i] %= mod;
            }
            for (int i = 1; i <= n; i++) {
                a[i] = s[n / i];
                //if (i <= 2*sqrt(n)) cout << i _ a[i] _ s[i] << endl;
            }
        }
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += a[i];
            ans %= mod;
        }
        cout << ans << endl;
        return 0;
    }
    else {
        vector<ll> c(3*int(sqrt(n)), 1);
        ll m = n / (int(sqrt(n)) + 1);
        if (int(sqrt(n)) == m) {
            //if (int(sqrt(n)) != m) assert(0);
            for (int i = 1; i <= m; i++) {
                c[2*m + 1 - i] = n / i - n / (i + 1);
            }
            vector<ll> a(3*int(sqrt(n)), 1);
            a.assign(3*int(sqrt(n)), 1);
            while (kc--) {
                vector<ll> s(3*m, 0);
                for (int i = 1; i <= 2*m; i++) {
                    if (i <= m) s[i] = a[i] + s[i - 1];
                    else s[i] = c[i] * a[i] + s[i - 1];
                    s[i] %= mod;
                }
                for (int i = 1; i <= 2*m; i++) {
                    a[i] = s[2*m - i + 1];
                    //cout << i _ a[i] << endl;
                }
            }

            ll ans = 0;
            for (int i = 1; i <= 2*m; i++) {
                ans += a[i]*c[i];
                ans %= mod;
            }
            
            cout << ans << endl;
        }
        else {
            //if (int(sqrt(n)) != m) assert(0);
            for (int i = 1; i <= m+1; i++) {
                c[2*m + 2 - i] = n / i - n / (i + 1);
            }
            vector<ll> a(3*int(sqrt(n)), 1);
            a.assign(3*int(sqrt(n)), 1);
            while (kc--) {
                vector<ll> s(3*m, 0);
                for (int i = 1; i <= 2*m+1; i++) {
                    if (i <= m) s[i] = a[i] + s[i - 1];
                    else s[i] = c[i] * a[i] + s[i - 1];
                    s[i] %= mod;
                }
                for (int i = 1; i <= 2*m+1; i++) {
                    a[i] = s[2*m - i + 2];
                    //cout << i _ a[i] << endl;
                }
            }

            ll ans = 0;
            for (int i = 1; i <= 2*m+1; i++) {
                ans += a[i]*c[i];
                ans %= mod;
            }
            
            cout << ans << endl;
        }
    }



    
}


Measured memory_bytes: 2456
#include <iostream>

using namespace std;

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

	if (a > b) {
		int t = a;
		a = b;
		b = t;
	}

	int c = b - a;
	if (c % 2 == 1) {
		cout << "IMPOSSIBLE" << endl;
	}
	else {
		cout << c / 2 + a << endl;
	}

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String S = sc.next();
		int x = 0;
		int max = 0;
		for (int i = 0 ; i < N ; i++) {
			if (S.charAt(i) == 'I') {
				x++;
			} else if (S.charAt(i) == 'D') {
				x--;
			}
			max = Math.max(max, x);
		}
		System.out.println(max);
	}
}


Measured memory_bytes: 21844
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long h = sc.nextLong();
        long w = sc.nextLong();
        long ans;
        if (h == 1 || w == 1) {
            ans = 1;
        } else {
            ans = h * w / 2 + h * w % 2;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

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

    long M = 1_000_000_007;
    int N = scanner.nextInt();
    int[] A = new int[N];
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int i = 0; i < N; i++) {
      A[i] = scanner.nextInt();
      cnt.put(A[i], cnt.getOrDefault(A[i], 0) + 1);
      if (cnt.getOrDefault(A[i], 0) > 3) {
        System.out.println(0);
        return;
      }
    }
    Map<Integer, Integer> freq = new HashMap<>();
    long res = 1;
    for (int i = 0; i < N; i++) {
      if (A[i] != 0) {
        int p = freq.getOrDefault(A[i] - 1, 0);
        if (p <= 0) {
          System.out.println(0);
          return;
        }
        res *= p;
        res %= M;
        freq.put(A[i] - 1, p - 1);
      }
      int c = freq.getOrDefault(A[i], 0);
      c++;
      freq.put(A[i], c);
    }
    if (cnt.get(0) > 1) {
      System.out.println(res * 6 % M);
    } else {
      System.out.println(res * 3 % M);
    }
  }
}


Measured memory_bytes: 72888
#include<bits/stdc++.h>
using namespace std;
#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n) REP(i,0,n)
#define all(obj) (obj).begin(),(obj).end()
typedef long long ll;
ll mod=1e9+7;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a,b,c,k;cin>>a>>b>>c>>k;
  if(a>=k)cout<<k<<endl;
  else if(a+b>=k)cout<<a<<endl;
  else cout<<a-(k-a-b)<<endl;
  return 0;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define INF 1e18

const ll mod = 1000000000+7;
const int N = 22;

int mat[N][N];
int dp[N][1<<N];

main()
{ 
	SPEED;
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n;
	cin >> n;
	for(int i = 0 ; i<n; i++)
	{
		for(int j = 0; j<n; j++)
		{
			cin >> mat[i][j];
		}
	}
	dp[0][0] = 1;
	for(int i = 1; i<=n; i++)
	{
		for(int j = 0; j<(1<<n); j++)
		{
			if(__builtin_popcount(j)!=i)continue;
			for(int k = 0; k<n; k++)
			{
				if(((1<<k)&j)!=0 && mat[i-1][k] == 1)
				{
					dp[i][j] += dp[i-1][j^(1<<k)];
					if(dp[i][j] >= mod)dp[i][j] -= mod;
				}
			}
		}
	}
	
	cout << dp[n][(1<<n)-1] << endl;
}

Measured memory_bytes: 178432
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin>>N;
  vector<int> a(N);
  for(int i=0;i<N;i++)
    cin>>a.at(i);
  sort(a.begin(),a.end());
  cout<<a.at(N-1)-a.at(0)<<endl;
}


Measured memory_bytes: 256
while True:
    n,x=map(int,input().split())
    if n==0 and x==0:
        break
    else:
        count=0
        for i in range(1,n-1):
            for j in range (i+1,n):
                for k in range (j+1,n+1):
                    if i+j+k==x:
                        count=count+1
    print(count)


Measured memory_bytes: 5592
#include <iostream>
#include <vector>
using namespace std;
int a, b, c, x, y, z, bef, cnt, ret;
vector <int> adj[100001];
bool visited[100001];
void dfs (int cur){
    visited[cur]=true;
    for (int i=0; i<adj[cur].size(); i++){
        if (!visited[adj[cur][i]]) dfs(adj[cur][i]);
    }
}
int check(){
    for (int i=bef; i<=a; i++){
        if (visited[i]==false){
            bef=i;
            return i;
        }
    }
    return -1;
}
int main(){
    cin>>a>>b;
    for (int i=1; i<=b; i++){
        cin>>x>>y>>z;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    bef=1;
    while (1){
        ret=check();
        if (ret==-1) break;
        dfs(ret);
        cnt++;
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 8960
#include<stdio.h>

#define ZUIDA 100000

int main(void){

    int N,M,L[ZUIDA],R[ZUIDA],i,j,tmp,L_max,R_min,result;

    scanf("%d %d",&N,&M);
    for(i = 0;i < M;i++){
        scanf("%d %d",&L[i],&R[i]);
    }

    L_max = L[0];
    R_min = R[0];

    for(i = 1;i < M;i++){
        if(L_max < L[i]){
            L_max = L[i];
        }
        if(R_min > R[i]){
            R_min = R[i];
        }
    }

    result = R_min - L_max;

    if(result >= 0){
        printf("%d",result + 1);
    }else{
        printf("0");
    }

    return 0;
}

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

int n;

int main(void){
	cin >> n;
	vector<int> a(n);
	rep(i, n){
		cin >> a[i];
		a[i]--;
	}
	lli ans = 0;
	rep(i, n){
		if(i == a[a[i]]) ans++;
	}
	cout << ans/2 << endl;
	return 0;
}


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

using namespace std;

#define all(x) x.begin(), x.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, m, n) for (int i = m; i <= n; ++i)

using i64 = long long;
using pii = pair<i64, i64>;

template<class A, class B>inline bool chmax(A &a, const B &b){return b > a ? a = b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b < a ? a = b,1 : 0;}

constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;

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

  int n, m, x;
  cin >> n >> m >> x;

  int right = 0;
  int left = 0;
  rep(i, m) {
    int a;
    cin >> a;
    if (a < x) ++left;
    else if (a > x) ++right;
  }

  cout << min(left, right) << "\n";

  return 0;
}

Measured memory_bytes: 256
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    X = SS()

    stk = []

    len_X = len(X)
    ans = len_X
    for i in range(len_X):
        if X[i] == 'S':
            stk.append('S')
        else:
            if stk and stk[-1] == 'S':
                stk.pop()
                ans -= 2

    print(ans)

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 10936
#include<stdio.h>
#include<string>
#include<iostream>

using namespace std;

int main(void){


 string n;

  cin >> n;

  if(n[1]==n[2]){
    if(n[0]==n[1]||n[2]==n[3]){
      printf("Yes\n");
    }
    else printf("No\n");
  }
    else{
      printf("No\n");

  }

return 0;



}


Measured memory_bytes: 256
_,a=open(0)
*a,=map(int,a.split())
m=max(a)
c=[0]*-~m
for i in a:c[i]+=1
print(sum(c[:-~m//2])<1and~m%-2+2==c[-~m//2]and all(c[i+1]>1for i in range(m//2,m))and'Possible'or'Impossible')

Measured memory_bytes: 38640
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<complex>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 100000007
typedef long long ll;
using namespace std;
vector<int> v;
int main(){
    ll n;
    cin>>n;
    while(n){
	v.push_back(n%10);
	n/=10;
    }
    bool ok=true;
    for(int i=0;i<v.size()-1;i++){
	if(v[i]!=9)ok=false;
    }
    if(ok)cout<<v[v.size()-1]+9*(v.size()-1)<<endl;
    else cout<<v[v.size()-1]+9*(v.size()-1)-1<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <cassert>
#include <functional>
#include <cstring>

using namespace std;

typedef pair<int, int> P;
#define mp make_pair
#define FOR(i, a, b) for(int (i)=a;(i)<(b);++(i))
#define rep(i, n)  FOR(i,0,n)
#define rrep(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define vsort(v) sort((v).begin(), (v).end());					//小さい順
#define rvsort(v) sort(v.begin(), v.end(),greater<int>());		//大きい順
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define all(c) (c).begin(),(c).end()
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vs vector<string>
#define vc vector<char>
#define vvc vector<vector<char>>
#define Print(p) cout<<(p)<<endl
#define F first
#define S second
#define pb push_back
#define mod 1000000007LL
#define INF 12345678901234567

const int maxn = 1e5 + 10;


//initialization here
//
int n, ma, mb;
int a[50], b[50], c[50];
int dp[50];
//
//initialization finish


// your function is here
//

//
// your function finished



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

	// your code is here
	//

	int a,c,b,d; cin >> a>>b>>c>>d;


	Print(max(a*b,c*d));

	//
	// your code finished
	return 0;
}

Measured memory_bytes: 256