akhauriyash/Code-Regression huggingface dataset:
n = int(input())
a = list(map(int, input().split()))

adj = 0
path = []

# aに正も負もあるとき
if any([ai > 0 for ai in a]) and any([ai < 0 for ai in a]):
    
    # |max| >= |min| ならmaxをすべてのaの要素に足せば、aはすべて0以上
    if abs(max(a)) >= abs(min(a)):
        max_a = max(a)
        max_idx = a.index(max_a) + 1
        
        for i, ai in enumerate(a):
            if i+1 == max_idx:
                pass
            else:
                a[i] += max_a    
                path.append((max_idx, i+1))
                
        adj = n-1
    
    # |max| < |min| ならminをすべてのaの要素に足せば、aはすべて0以下    
    else:
        min_a = min(a)
        min_idx = a.index(min_a) + 1
        
        for i, ai in enumerate(a):
            if i+1 == min_idx:
                pass
            else:
                a[i] += min_a   
                path.append((min_idx, i+1))
            
        adj = n-1
        
        

# aがすべて0以上なら累積和の要領で足すようにする
if all([ai >= 0 for ai in a]):
    print(n-1 + adj)
    for i in range(1,n):
        path.append((i, i+1))
        
    for x,y in path:
        print(x,y)
        
# aがすべて0以下なら、a_nから順に累積和の要領で足していく
elif all([ai <= 0 for ai in a]):
    print(n-1 + adj)
    for i in range(n,1,-1):
        path.append((i, i-1))
        
    for x,y in path:
        print(x,y)

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

int main() {
	// your code goes here
	int n,k;
	cin>>n>>k;
	vector<int>a(n,0);
	for(int i=0;i<k;i++)
	{
		int d;
		cin>>d;
		int x;
		while(d--)
		{
			cin>>x;
			a[x-1]++;
		}
	}
	int ans=0;
	for(int i=0;i<n;i++)
	{
		if(a[i]==0)
		ans++;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0, i_l = (int)n; i < i_l; i++)
#define loop(i, a, b) for (int i = a; i < (int)(b); i++)
 
const int MAX_COUNT = 5000;
ll N, K;
ll A[MAX_COUNT];
ll accum[MAX_COUNT];
set<ll> requiredNum;

ll searched[MAX_COUNT + 1][MAX_COUNT + 1];

 
void search(int from, ll value) {
    if (searched[from][value] > 0) {
        return;
    }
    searched[from][value] = 1;

    ll start = 0;
    if (from > 0) {
        start = accum[from - 1];
    }
    ll *left = lower_bound(accum + from, accum + N, value + start);
    if (left == accum + N) {
        return;
    }
    ll *right = upper_bound(accum + from, accum + N, value + start);
    int idx = left - accum;
    int nextIdx = right - accum + 1;
    for (int i = from; i <= idx && i < N; i++) {
        ll num = A[i];
        requiredNum.insert(num);
        search(nextIdx, min(num, value));
    }
}
int main() {
    cin >> N >> K;
    rep(i, N) cin >> A[i];
 
    //累積和
    sort(A, A + N, greater<ll>());
    accum[0] = A[0];
    loop(i, 1, N) {
        accum[i] = accum[i - 1] + A[i];
    }
    rep(i, N) {
        search(i, K);
    }
 
    //不要数をカウント
    int count = 0;
    rep(i, N) {
        if (requiredNum.find(A[i]) == requiredNum.end()) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 193792
//ARC075-C(Bugged)
#include<iostream>
using namespace std;

//i問について一つ一つやっていると当然間に合わない
//dpを考える
//10の倍数については最後に考えればいける
int N;
int score[110];
int dp[110][10010]={};
//dp[i][j]:i番目までの問題でj点が作れるか

int main(){
    
    cin>>N;
    for(int i=0; i<N; i++)cin>>score[i];
    
    //dp初期条件
    for(int i=0; i<=N; i++)dp[i][0]=1;
    
    for(int i=0; i<N; i++){
        for(int j=0; j<=10000; j++){
            //dp漸化式:dp[i+1][j]=max(dp[i][j-score[i]],dp[i][j])
            if(j-score[i]>=0)dp[i+1][j]=max(dp[i][j-score[i]],dp[i][j]);
            else dp[i+1][j]=dp[i][j];
        }
    }
    
    int ans=10000;
    for(int t=10000; t>=0; t--){
        if(dp[N][t]==1 && t%10!=0){ans=t;break;}
        if(t==0)ans=t;
    }
    
    cout<<ans<<endl;
    return 0;
}

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

typedef long long ll;
typedef long double ld;
#define REP(i, n) for (int i = 0; i < n; i++)

/* print like python */
void print() {cout << endl;}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head; if (sizeof...(tail) != 0) cout << " "; print(forward<Tail>(tail)...);}
template <class T> void print(vector<T> &vec) { for (auto& a : vec) { cout << a; if (&a != &vec.back()) cout << " "; } cout << endl; }
template <class T> void print(vector<vector<T>> &df) { for (auto& vec : df) { print(vec); } }

int main()
{
    int n;
    int ans=0;
    int mod[5];
    REP(i,5){
        int v;
        cin >> v;
        ans += v;
        mod[i] = v%10==0?0:10-v%10;
    }
    sort(mod, mod+5);
    REP(i,4){
        ans += mod[i];
    }
    print(ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int gi() {
    int x=0,o=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int n;
ll a[N],b[N];
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=gi(),b[i]=gi();
    ll ans=0;
    for(int i=n;i;i--) {
        ll tmp=b[i]-((a[i]+ans-1+b[i])%b[i]+1);
        ans+=tmp;
    }
    printf("%lld\n",ans);
    return 0;
}
//orzgzy
//鸡贼明年进队超稳


Measured memory_bytes: 1792
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Random;
import java.util.Scanner;
public class Main {
	static Scanner sc = new Scanner(System.in);static void p(int i) {System.out.println(i);}static void p(long i) {System.out.println(i);}static void p(String i) {System.out.println(i);}static void p(double i) {System.out.println(i);}
	
	
	public static void main(String[] args) {
		
		long K=sc.nextInt();
		long A=sc.nextInt();
		long B=sc.nextInt();
		
		long ans=0;
		if(B-A>2) {
			long v=K-(A-1);
			ans+=A+(B-A)*((int)v/2)+v%2;
		}else {
			ans+=K+1;
		}
		p(ans);
		
	}
	
}
	


Measured memory_bytes: 23892
#include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define sz(v) (int) v.size()
#define pr(v) For(i, 0, sz(v)) {cout<<v[i]<<" ";} cout<<endl;
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define int long long
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
typedef vector<int> vi;
#define MOD 1000000007
#define INF 1000000000000000007LL

const int N = 100005;
 
// it's swapnil07 ;)
 
#ifdef SWAPNIL07
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
#else
#define endl '\n'
#define trace(...)
#define end_routine()
#endif

int factors(int n){
    int a = -1;
    for(int i=1; i*i<=n; i++){
        if(n%i!=0){
            continue;
        }
        a+=2;
        if(i*i==n){
            a--;
        }
    }
    return a;
}

signed main()
{
    fast
    #ifdef SWAPNIL07
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif  
    int n; cin>>n;
    int ans = 1;
    ans += factors(n-1);
    for(int i=2; i*i<=n; i++){
        int z=n;
        while(z%i==0){
            z/=i;
            if((z-1)%i==0){
                ans++;
            }
        }
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long; using pint = pair<int, int>; using pll = pair<ll, ll>;
const long long MOD = 1000000007;

long long gcd(long long a, long long b){
    while (a != 0 && b != 0){
        if (a >= b) a %= b;
        else b %= a;
    }
    return a + b;
}

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

ll N, M, a[100010];

signed main(){
    cin >> N >> M;
    REP(i, N) cin >> a[i];
    ll L = 1;
    REP(i, N){
        L = lcm(L, a[i] / 2);
        if(L < 0){
            PRINT(0);
            return 0;
        }
    }
    REP(i, N){
        if(L / (a[i] / 2) % 2 != L / (a[0] / 2) % 2){
            PRINT(0);
            return 0;
        }  
    }
    if(M < L) PRINT(0);
    else PRINT((M - L) / (2 * L) + 1);
    return 0;
}

Measured memory_bytes: 4380
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF 1e18
#define INF 1e9
using namespace std;

#define fs first
#define sc second

using P = pair<ll,ll>;
using Pll = pair<P,ll>;
using PQ = priority_queue<P,vector<P>,greater<P>>;


const ll MOD = 1e9+7;
 

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

    rep(i,0,s.size()){
        if(s[i] == '?')s[i] = 'D';
    }

    cout << s << endl;
    return 0;
}


Measured memory_bytes: 3752
from collections import deque
N, M = map(int, raw_input().split())
G = dict()
for n in range(N):
    L = map(int, raw_input().split())
    # Agent
    G['A'+str(n+1)] = {'con':False, 'edge':map(str, L[1:])}
    for l in L[1:]:
        if G.has_key(str(l)) == False:
            G[str(l)] = {'con':False, 'edge':['A'+str(n+1)]}
        else:
            G[str(l)]['edge'].append('A'+str(n+1))


queue = deque(['A1'])
G['A1']['con'] = True

while len(queue) > 0:
    q = queue.popleft()
    for p in G[q]['edge']:
        if G[p]['con']:
            pass
        else:
            G[p]['con'] = True
            queue.append(p)
res = 'YES'
for n in range(N):
    if G['A'+str(n+1)]['con'] == False:
        res = 'NO'
        break
print res

Measured memory_bytes: 66836
import sys
import math
import numpy as np
def I():return int(sys.stdin.readline().replace("\n",""))
def I2():return map(int,sys.stdin.readline().replace("\n","").split())
def S():return str(sys.stdin.readline().replace("\n",""))
def L():return list(sys.stdin.readline().replace("\n",""))
def Intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def Lx(k):return list(map(lambda x:int(x)*-k,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":
    n,d = I2()
    cnt = 0
    for i in range(n):
        x,y = I2()
        if d >= math.sqrt(x*x+y*y):
            cnt += 1
    print(cnt)

Measured memory_bytes: 27152
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define RFOR(i,a,b) for(int i=(b-1); i>=(a); i--)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define pb push_back
using ll = long long;
using D = double;
using LD = long double;
using P = pair<int, int>;
const int mod = 1e9+7;
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; }

const int inf = 1e9;
int dp[1000005][2];

int main(){
    string s; cin >> s;
    s += '0';
    int n = s.size();
    rep(i,n+1)rep(j,2) dp[i][j] = inf;
    dp[0][0] = 0;
    rep(i,n)rep(j,2){
        int d = s[i] - '0';
        if(j == 1) d++;
        rep(na, 10){
            int ni = i+1, nj = 0;
            int nb = na - d;
            if(nb < 0) {
                nj = 1;
                nb += 10;
            }
            chmin(dp[ni][nj], dp[i][j] + na + nb);
        }
    }
    cout << dp[n][0] << endl;
}


Measured memory_bytes: 9220
#define _CRT_SECURE_NO_WARNINGS

/* include ***********************/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

/* define *************************/
//for
#define REP(i,n) for(int i=0,i##_len=(int)(n);i<i##_len;i++)
#define REPS(i,n) for(int i=1,i##_len=(int)(n);i<=i##_len;i++)
#define RREP(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define RREPS(i,n) for(int i=(int)(n);i>0;i--)
#define FOR(i,s,n) for(int i=(int)(s),i##_len=(int)(n);i<i##_len;i++)
#define RFOR(i,s,n) for(int i=(int)(s)-1,i##_len=(int)(n);i>=i##_len;i--)

//printf
#define PRINTD(d) printf("%d\n",(d))
#define PRINTL(d) printf("%lld\n",(d))

//memset
#define m0(s) memset(s,0,sizeof(s))
#define ml(s) memset(s,63,sizeof(s))
#define fill(s,c) memset(s,c,sizeof(s))

#define INF 1e9
#define MOD 1000000007

typedef long long ll;
typedef unsigned long long ull;

int a[1000000];

int diff[4][2] = {
	{ 0, -1 },
	{ -1, 0 },
	{ 1, 0 },
	{ 0, 1 },
};

int Min(int a, int b) {
	return (a)<(b) ? (a) : (b);
}
int Max(int  a, int  b) {
	return (a) > (b) ? (a) : (b);
}
void Swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

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

	a[s] = 1;
	int cnt = 1;
	while (1) {
		cnt++;
		if (s % 2) {
			s = 3 * s + 1;
		}
		else {
			s = s / 2;
		}
		if (a[s]) {
			PRINTD(cnt);
			return 0;
		}
		a[s] = 1;
	}
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define pb push_back
#define si second
#define int long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define  mod 100000000000
#define double long double
#define all(o) o.begin(),o.end()
using namespace std;

int power(int x, int y)
{
    int res = 1;
    x = x % mod;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % mod;
        y = y>>1; // y = y/2
        x = (x*x) % mod;
    }
    return res%mod;
}
int inv(int n)
{
    return power(n,mod-2)%mod;
}



int32_t main() {

  //  fast

    int c=0,n,ele,i;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>ele;
        if(ele%2 && i%2)
            c++;
    }
    cout<<c<<"\n";
}


Measured memory_bytes: 3588
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>

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

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; }

typedef long long ll;

using namespace std;
int h,w;
vector<string> hw(400);
vector<vector<int>> used(400,vector<int>(400,0));
int dx[4]={0,1,0,-1};
pair<int,int> dfs(int y,int x)
{
  used[y][x]=1;
  int bl=0,wh=0;
  if(hw[y][x]=='#')bl++;
  else wh++;
  rep(i,4)
  {
    int ny=y+dx[i],nx=x+dx[i^1];
    if(ny<0||ny>=h||nx<0||nx>=w)continue;
    if(used[ny][nx])continue;
    if(hw[ny][nx]==hw[y][x])continue;
    auto t=dfs(ny,nx);
    bl+=t.first;
    wh+=t.second;
  }
  return {bl,wh};
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin>>h>>w;
  rep(i,h)cin>>hw[i];
  ll res=0;
  rep(i,h)rep(j,w)if(!used[i][j]){auto t=dfs(i,j);res+=(ll)t.first*t.second;}
  cout<<res<<endl;


  return 0;

}


Measured memory_bytes: 16128
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;


int main(){
    ll a, b;
    cin >> a >> b;
    cout << a * b << endl;
    return 0;
}


Measured memory_bytes: 3636
K = int(input())
 
from collections import deque
q = deque(range(1, 10))
for _ in range(K - 1):
    d = q.popleft()
    if d % 10 > 0:
        q.append(d * 10 + d % 10 - 1)
    q.append(d * 10 + d % 10)
    if d % 10 < 9:
        q.append(d * 10 + d % 10 + 1)
print(q.popleft())


Measured memory_bytes: 11912
package main

import "fmt"

func main() {
    var n, a int
    var nums [100]int

    fmt.Scanf("%d", &n)

    // 読み込み
    for i:=0; i<n; i++ {
        fmt.Scanf("%d", &a)
        nums[i] = a
    }

    // 反転
    for i:=0; i<n/2; i++ {
        nums[i], nums[n-i-1] = nums[n-i-1], nums[i]
    }

    // 表示
    for i:=0; i<n; i++ {
        fmt.Printf("%d", nums[i])
        if i != n-1 {
            fmt.Print(" ")
        }
    }
    fmt.Println("")
}


Measured memory_bytes: 1128
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int main(){
    int n;
    int ans=0;
    cin >> n;
    vector<int> v(n);
    vector<int> c(n);
    for(int i=0;i<n;i++){
        cin >> v[i];
    }
    for(int i=0;i<n;i++){
        cin >> c[i];
    }
    for(int i=0;i<n;i++){
        if(v[i] - c[i] > 0){
            ans += v[i] - c[i];
        }
    }
    cout << ans << endl;

}

Measured memory_bytes: 256
// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
static immutable MOD=10^^9+7;alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std, core.bitop;
// dfmt on

void main()
{
    long N = lread();
    alias T = Tuple!(long, char[]);
    DList!T Q;
    Q.insert(T(1, repeat('a').take(N).array()));
    while (!Q.empty)
    {
        auto t = Q.front;
        Q.removeFront();
        if (t[0] == N)
        {
            writeln(t[1]);
            continue;
        }
        char c = 'a';
        foreach (i; 0 .. t[0])
            if (c < t[1][i])
                c = t[1][i];
        foreach (char x; 'a' .. cast(char)(c + 2))
        {
            auto s = t[1].dup;
            s[t[0]] = x;
            Q.insertBack(T(t[0] + 1, s));
        }
    }
}


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

int main()
{
    char c;
    cin >> c;
    if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
        cout << "vowel" << endl;
    } else {
        cout << "consonant" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var s, t string
	count := 0
	fmt.Scan(&s, &t)

	S := make([]string, len([]rune(s)))
	T := make([]string, len([]rune(t)))

	for pos, value := range s {
		S[pos] = string(value)
	}

	for pos, value := range t {
		T[pos] = string(value)
		if S[pos] != T[pos] {
			count++
		}
	}
	fmt.Println(count)
}


Measured memory_bytes: 9972
#include "bits/stdc++.h"
using namespace std;


const int D = 80 * 160 + 10;
const int D2 = D * 2;
typedef bitset<D2> bs;
bs dp[90][90];

int main() {
	int H, W;
	cin >> H >> W;
	vector<vector<int>> A(H, vector<int>(W));
	vector<vector<int>> B(H, vector<int>(W));
	vector<vector<int>> AB(H + 1, vector<int>(W + 1));
	for (int n = 0; n < H; ++n) {
		for (int m = 0; m < W; ++m) {
			cin >> A[n][m];
		}
	}
	for (int n = 0; n < H; ++n) {
		for (int m = 0; m < W; ++m) {
			cin >> B[n][m];
		}
	}
	for (int n = 0; n < H; ++n) {
		for (int m = 0; m < W; ++m) {
			AB[n][m] = abs(A[n][m] - B[n][m]);
		}
	}

	dp[0][0][D - AB[0][0]] = 1;
	dp[0][0][D + AB[0][0]] = 1;

	for (int n = 0; n < H; ++n) {
		for (int m = 0; m < W; ++m) {
			if (n != 0) {
				dp[n][m] |= dp[n - 1][m] << AB[n][m];
				dp[n][m] |= dp[n - 1][m] >> AB[n][m];
			}
			if (m != 0) {
				dp[n][m] |= dp[n][m - 1] << AB[n][m];
				dp[n][m] |= dp[n][m - 1] >> AB[n][m];
			}
		}
	}
	int ans = D2;
	for (int n = 0; n < D2; ++n) {
		if (dp[H - 1][W - 1][n]) {
			ans = min(ans, abs(n - D));
		}
	}

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

Measured memory_bytes: 24060
from math import ceil

r, g, b, n = map(int, input().split())
cnt = 0
for i in range(ceil(n / r) + 1):
    for j in range(ceil(n / g) + 1):
        if i * r + j * g > n:
            break
        if i * r + j * g == n:
            cnt += 1
            continue
        else:
            tmp = n - (i * r + j * g)
            if tmp % b == 0:
                cnt += 1
print(cnt)


Measured memory_bytes: 41564
N = int(input())
A = list(map(int,input().split()))
MOD = 1000000007
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr

lcma={}
for ai in A:
  f=factorization(ai)
  for fi in f:
    if fi[0] in lcma:
      lcma[fi[0]]=max(lcma[fi[0]],fi[1])
    else:
      lcma[fi[0]]=fi[1]
l=1
for k,v in lcma.items():
  l*=pow(k,v,MOD)
  l%=MOD
ans=0
for ai in A:
  ans+=l*pow(ai,MOD-2,MOD)
  ans%=MOD

print(ans)


Measured memory_bytes: 4596
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int a,b; cin>>a>>b;
	cout<<(a*b)<<endl;	
	return 0;
}


Measured memory_bytes: 3596
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

int query(vector<int> &x){
    cout<<"?";
    rep(i,x.size()) cout<<" "<<x[i]+1;
    cout<<endl;

    string t;
    cin>>t;
    if(t=="Red") return 1;
    else if(t=="Blue") return 2;
    else exit(0);
}

int main(){
    int N;
    cin>>N;

    vector<int> reds,blues;
    vector<int> v;
    rep(i,N) v.push_back(i);
    int lef=query(v);
    int rig=3-lef;
    int ok=N,ng=0;
    while(abs(ok-ng)>1){
        int mid=(ok+ng)/2;
        vector<int> v;
        rep(i,N) v.push_back(mid+i);
        int c=query(v);
        if(c==rig) ok=mid;
        else ng=mid;
    }

    if(lef==1){
        reds.push_back(ng);
        blues.push_back(ng+N);
    }else{
        blues.push_back(ng);
        reds.push_back(ng+N);
    }

    v.clear();
    for(int i=0;i<N-1;i++) v.push_back(ok+i);

    for(int i=0;i<2*N;i++){
        if(ng<=i&&i<=ng+N) continue;
        v.push_back(i);
        int c=query(v);
        if(c==1) reds.push_back(i);
        else blues.push_back(i);
        v.pop_back();
    }

    v.clear();
    for(int i=0;i<N/2;i++){
        v.push_back(reds[i]);
        v.push_back(blues[i]);
    }
    for(int i=ng+1;i<ng+N;i++){
        v.push_back(i);
        int c=query(v);
        if(c==1) reds.push_back(i);
        else blues.push_back(i);
        v.pop_back();
    }

    string ans(2*N,'p');
    rep(i,N){
        ans[reds[i]]='R';
        ans[blues[i]]='B';
    }
    cout<<"! "<<ans<<endl;

  return 0;
}


Measured memory_bytes: 724
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    ll n,d;
    cin >> n >> d;
    vector<ll>x(n),y(n);
    REP(i,n)cin >> x[i] >> y[i];
    int answer = 0;
    REP(i,n){
        if(x[i]*x[i]+y[i]*y[i] <= d*d)answer++;
    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 6340
A,B,M = map(int,input().split())

from collections import defaultdict

a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

MINB = min(b)

wari = defaultdict(list)
for _ in range(M):
    x,y,c = map(int,input().split())
    wari[x-1].append((y-1,c))

ans = float("inf")
for i in range(A):
    tmp = a[i] + MINB
    for y,c in wari[i]:
        tmp = min(tmp, a[i] + b[y] - c)
    ans = min(ans, tmp)

print(ans)

Measured memory_bytes: 44476
#include <stdio.h>

int main (void){
	int x = 0, y = 0;
	scanf("%d %d", &x, &y);

	int group[12] = {1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1};

	if(group[x-1] == group[y-1]) printf("Yes\n");
	else printf("No\n");

	return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;


public class Main {

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

		int N = sc.nextInt();
		int[][] A = new int[N][3];

		for(int i = 0 ; i < N ; i++){
			A[i][0] = sc.nextInt();
			A[i][1] = sc.nextInt();
			A[i][2] = sc.nextInt();

		}
		sc.close();

		long[][] cost = new long[N][3];
		cost[0][0] = A[0][0];
		cost[0][1] = A[0][1];
		cost[0][2] = A[0][2];

		System.out.println(dfs(0,N-1,cost,A));
	}
	static long dfs(int a,int b,long[][] c,int[][] d){
		if(a == 0){
			return dfs(1,b,c,d);
		}
		else if(b==0){
			return Math.max(Math.max(d[b][1], d[b][2]),d[b][0]);
		}
		else{
			d[a][0] = d[a][0] + Math.max(d[a-1][1],d[a-1][2]);
			d[a][1] = d[a][1] + Math.max(d[a-1][0],d[a-1][2]);
			d[a][2] = d[a][2] + Math.max(d[a-1][0],d[a-1][1]);

			if(a == b){
				return Math.max(d[a][0],Math.max(d[a][1], d[a][2]));
			}
			else{
				return dfs(a+1,b,c,d);
			}
		}
	}
}

Measured memory_bytes: 110848
function Main(input) {
    // inputにはすべての入力の文字列が与えられるので必要に応じて input.split("\n") などで分割する。

    var data = input.split("\n")

    var first_line = data[0].split(" ")
    var second_line = data[1].split(" ")

    const sum = second_line.map(x => parseInt(x)).reduce((acc, cur) => acc + cur, 0);
    const h = first_line[0];
    if(sum >= h){
      console.log('Yes')
    } else {console.log('No')};


}

// Don't edit this line!
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 16716
import java.util.*;

public class Main
{
    public static void main(String... args){
        Scanner sc= new Scanner(System.in);
        String s = sc.next();
        int first = -1;
        int last = -1;
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i);
            if (c == 'A' && first == -1){
                first = i;
            } else if (c == 'Z'){
                last = i;
            }
        }
        System.out.println(last - first + 1);
    }

}

Measured memory_bytes: 27100
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long ll;
int main(void){
  string S, T;
  cin >> S >> T;
  int N = S.size(), ans = 0;
  for(int i = 0; i < N; i++){
    if(S[i] != T[i]){
      ans++;
    }  
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3924
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner s = new Scanner(System.in);
		String n_m = s.nextLine();
		String[] conditions = n_m.split("\\s");
		int n = Integer.parseInt(conditions[0]);
		int m = Integer.parseInt(conditions[1]);
		
		HashMap<Integer, List<Integer>> ships = new HashMap<>();
		for(int i = 0; i < m; i++) {
			int from = s.nextInt();
			int to = s.nextInt();
			
			List<Integer> value = ships.get(from);
			if(value == null) {
				value = new ArrayList<>();
				value.add(to);
				ships.put(from, value);
			} else {
				value.add(to);
			}
		}
		
		boolean possible = false;
		
		List<Integer> transits = ships.get(1);
		for(Integer transit : transits) {
			if(ships.containsKey(transit)) {
				List<Integer> goals = ships.get(transit);
				for(Integer goal : goals) {
					if(goal == n) {
						possible = true;
					}
				}
			}
		}
		if(possible) {
			System.out.println("POSSIBLE");
		} else {
			System.out.println("IMPOSSIBLE");
		}
	}
}


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

typedef long double ld;
typedef unsigned long ul;
typedef long long ll;
typedef unsigned long long ull;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long> vl;
typedef vector<double> vd;
typedef map<int,int> mii;
typedef pair<int,int> pii;
typedef pair<long,long> pll;

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,a,n) for(int i=a;i<n;i++)
#define ALL(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))

#define pi 3.14159265358979
#define eps 1e-9
#define inf 1<<30

#define P 1000000007

int n[2];
ll x[2][100010];

int main()
{
	ll ret[2] = {0,0};

	cin >> n[0] >> n[1];
	rep(i,2)rep(j,n[i]) cin >> x[i][j];

	rep(i,2)rep(j,n[i]-1){
		ll cnt = (ll)(j+1) * (n[i]-1-j) % P;
		cnt = cnt * (x[i][j+1] - x[i][j]) % P;
		ret[i] = ( ret[i] + cnt ) % P;
	}

	printf("%lld\n", ret[0] * ret[1] % P );

	return 0;
}


Measured memory_bytes: 1920
N = int(input())
B = list(map(int,input().split()))
A = [0]*N

A[0] = B[0]
A[N-1] = B[N-2]

for i in range(N-2):
  if B[i] <= B[i+1]:
    A[i+1] = B[i]
  else:
    A[i+1] = B[i+1]
    
print(sum(A))

Measured memory_bytes: 9056
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

K=int(input())
print('ACL'*K)

Measured memory_bytes: 61716
N,M=map(int,input().split())
a=[int(input()) for i in range(M)]
a=set(a)
dp=[0]*(N+1)
dp[0]=1
inf=10**9+7
if 1 not in a:
  dp[1]=1
else:
  dp[1]=0
for i in range(2,N+1):
  if i in a:
    continue
  else:
    dp[i]=dp[i-1]+dp[i-2]
ans=dp[N]%inf
print(ans)


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

#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define RFOR(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define LL long long
#define INF INT_MAX/3

const double EPS = 1e-14;
const double PI  = acos(-1.0);


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

  vector<int> a(n);
  REP (i, n) {
    scanf("%d", &a[i]);
  }

  LL ans = pow(10, 18);
  REP (j, 2) {
    LL sum = 0;
    LL cnt = 0;
    REP (i, n) {
      sum += a[i];
      int pm = ((i + j) % 2) ? 1 : -1;
      if (pm * sum <= 0) {
        cnt += abs(pm * 1 - sum);
        sum = pm * 1;
      }
    }
    ans = min(ans, cnt);
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define FOR(i,b,e) for (common_type_t <decltype (b), decltype (e)> i = (b), i ## __end = (e); i < i ## __end; ++ i)
#define FORR(i,b,e) for (common_type_t <decltype (b), decltype (e)> i = (e), i ## __begin = (b); i -- > i ## __begin;)
#define rep(i,n) for (decay_t <decltype (n)> i = 0, i ## __len = (n); i < i ## __len; ++ i)
#define ALL(x) begin (x), end (x)
using namespace std;

auto main () -> int
{
  cin.tie (nullptr);
  ios::sync_with_stdio (false);

  size_t n;
  cin >> n;

  double ans = 0;

  rep (i, n)
  {
    double a;
    cin >> a;
    ans += 1.0 / a;
  }
  cout << 1.0 / ans << endl;
}


Measured memory_bytes: 256
// Problem : A - Not
// Contest : AtCoder - AtCoder Beginner Contest 178
// URL : https://atcoder.jp/contests/abc178/tasks/abc178_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
using namespace std;

/* DEBUGGING */
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define deb(x...)
#endif

/* MACROS */ 
typedef long long int ll;
 
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
 
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

typedef map<int,int> mii;

#define  ff          first
#define  ss          second
#define  pb          push_back
#define  IOS         ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define  lb          lower_bound
#define  ub          upper_bound
#define  all(x)      (x).begin(), (x).end()
#define  lcm(x, y)   ((x) * (y) / __gcd(x, y))
#define  ps(x,y)     fixed<<setprecision(y)<<x
#define  setbit(x)   __builtin_popcountll(x)
#define  rep(i,a,b)  for(int i=a ; i<b ; ++i)
#define  repr(i,a,b) for(int i=a ; i>=b ; --i)

/* CONSTANTS */ 
#define PI 3.141592653589793
const ll MOD = 1e9 + 7;
const ll INF = 1000000000;
const ll MAX_N = 2e5 + 2;

// #define cerr if(false)cerr
/* CODE STARTS HERE */

void solve(){
    int n; cin >> n;
    cout << !n;
}

int main(){
    IOS;
    solve();
}

Measured memory_bytes: 3616
import itertools
import math


def main():
    n = int(input())
    town = [i for i in range(1, n + 1)]
    comb = list(itertools.permutations(town))
    pos = []
    for i in range(n):
        pos.append(list(map(int, input().split())))
    calc = []
    for c in comb:
        tmp = 0
        for i in range(0, len(c) - 1):
            tmp += distance(pos[c[i] - 1], pos[c[i + 1] - 1])
        calc.append(tmp)
    mea = sum(calc) / len(calc)
    print(mea)


def distance(p, pp):
    return math.sqrt(((p[0] - pp[0]) **2) + ((p[1] - pp[1]) **2))


if __name__ == '__main__':
    main()

Measured memory_bytes: 9252
x,y = map(int , input().split())

t = 2
k = 4

flg = False
for i in range(x):
    if t*i + k*(x-i) == y or t*(x-i) + k*i == y:
        flg = True

if flg == True:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 9200
// J4180449 三宅亮輔
// 問題名
// - Reverse Polish Notation
// 問題URL
// - https://onlinejudge.u-aizu.ac.jp/#/problems/ALDS1_3_A
// 所要時間
// - 30分
// 学んだこと
//  一行に任意の数の文字列を読み取る方法がwhile(cin>>str)であることを学んだ
//  空白で区切るpythonのsplitのようなものがないことを学んだ
//  stackの使い方を学んだ

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
stack<ll> s;
string str;
int main() {
    while(cin >> str) {
        if(str == "+" || str == "-" || str == "*") {
            ll b = s.top();
            s.pop();
            ll a = s.top();
            s.pop();

            if(str == "+")
                s.push(a + b);
            if(str == "-")
                s.push(a - b);
            if(str == "*")
                s.push(a * b);
        } else {
            s.push(stoi(str));
        }
    }
    cout << s.top() << endl;
}


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

bool bit[21] = {false,};

void func(ll num){
    ll t = num;
    for(int i = 0; i < 21; i++){
        if(t&1){bit[i] = false;}
        t = t >> 1;
    }
}

int main(){
    int n;
    cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int l=0, r=0;
    ll ans = (ll)n;


    for(int i = 0; i < n; i++){
        ll t = a[i];
        int j;
        for(j = 0; j < 21; j++){
            if(t&1){
                if(bit[j] == true){
                    func(a[l]);
                    l++;
                    i--;
                    break;
                }
            }
            t = t>>1;
        }
        if(j==21){
            ans += (ll)i-(ll)l;
            ll t = a[i];
            for(j = 0; j < 21; j++){
                if(t&1){bit[j] = true;}
                t = t>>1;
            }
        }
    }
    cout << ans << endl;


    return 0;

}


Measured memory_bytes: 1792
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <math.h>
# include <algorithm>
using namespace std;
# define pi acos(-1.0)
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
typedef long long LL;
typedef unsigned long long ULL;

int a[105];

int main()
{
    int n,max=0,min=1000;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(max<a[i])max=a[i];
        if(min>a[i])min=a[i];
    }
    cout<<max-min<<endl;
    return 0;
}





















Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))

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

    string s; cin >> s;
    int pa = 0;
    rep(i, s.size()) {
        if (s[i] == 'p') {
            pa++;
        }
    }

    cout << s.size() / 2 - pa << endl;

    return 0;
}


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

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)(a).size()
#define mp(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ll IINF = INT_MAX;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    ll a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    if (a[n - 1] == 0 && (k & 1)) {
        cout << 0 << '\n';
        exit(0);
    }
    ll ans = 1;
    if (a[n - 1] < 0 && (k & 1)) {
        for (int i = n - 1; i >= 0; i--) {
            if (a[i] < 0) a[i] += MOD;
            ans *= a[i];
            ans %= MOD;
            if (ans < 0) ans += MOD;
            k--;
            if (k == 0) break;
        }
        cout << ans << '\n';
        exit(0);
    }
    int l = 0, r = n - 1;
    if (k & 1) {
        a[r] %= MOD;
        if (a[r] < 0) a[r] += MOD;
        ans *= a[r];
        ans %= MOD;
        if (ans < 0) ans += MOD;
        r--;
        k--;
    }
    k /= 2;
    for (int i = 0; i < k; i++) {
        ll le = a[l] * a[l + 1];
        ll ri = a[r] * a[r - 1];
        if (le > ri) {
            le %= MOD;
            if (le < 0) le += MOD;
            ans *= le;
            ans %= MOD;
            if (ans < 0) ans += MOD;
            l += 2;
        } else {
            ri %= MOD;
            if (ri < 0) ri += MOD;
            ans *= ri;
            ans %= MOD;
            if (ans < 0) ans += MOD;
            r -= 2;
        }
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 5176
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MOD 1000000007
#define PI 3.141592653589793
const int INF = 100000000;
int dx[] = {0,1,-1,0,1,-1,1,-1};
int dy[] = {1,0,0,-1,1,-1,-1,1};

int main(){
    int n;
    scanf("%d", &n);
    ll sum1 = 0, sum2 = 0;
    ll ans1 = 0, ans2 = 0;
    for(int i = 0; i < n; i++){
        ll a;
        scanf("%lld", &a);
        sum1 += a;
        sum2 += a;
        if(i % 2){
            if(sum1 >= 0){
                ans1 += sum1 + 1;
                sum1 = -1;
            }
            if(sum2 <= 0){
                ans2 += abs(sum2) + 1;
                sum2 = 1;
            }
        }else{
            if(sum1 <= 0){
                ans1 += abs(sum1) + 1;
                sum1 = 1;
            }
            if(sum2 >= 0){
                ans2 += sum2 + 1;
                sum2 = -1;
            }
        }
    }
    printf("%lld\n", min(ans1, ans2));
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define rep2(i,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


int main() {
    int d, n;
    cin >> d >> n;

    int count = 0;
    rep(i, INF) {
        int num = i+1;
        int div = 0;
        while (num%100 == 0) {
            if (num == 0) break;
            num /= 100;
            div++;
        }
        if (div == d) count++;
        if (n == count) {
            cout << i+1 << endl;
            return 0;
        }
    }

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};

int N,A[100010];


signed main(){
  cin>>N;
  for(int t=1;t<=N;t++)cin>>A[t];
  A[0]=0;
  A[N+1]=0;

  int sum=0;
  for(int t=0;t<=N;t++){
    sum+=abs(A[t+1]-A[t]);
  }

  for(int i=1;i<=N;i++){
    int ans=sum;
    int s=min(A[i-1],A[i+1]);
    int l=max(A[i-1],A[i+1]);

    if(s<=A[i]&&A[i]<=l){
      cout<<ans<<"\n";
    }else{
      if(l<A[i]){
        cout<<ans-2*abs(l-A[i])<<"\n";
      }else if(s>A[i]){
        cout<<ans-2*abs(s-A[i])<<"\n";
      }
    }

  }

  return 0;
}


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

int main(int argc, char const *argv[])
{
    int a, b;
    cin >> a >> b;
    if(13 <= a) {
        cout << b << endl;
    } else if(6 <= a) {
        cout << b / 2 << endl;
    } else {
        cout << 0 << endl;
    }
    return 0;
}


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

int main(){
    int N,min=100000000,wa=0;
    cin >> N;
    vector<int> P(N);

    for(int i = 0;i < N;i++){
        cin >> P.at(i);
    }

    for(int i = 0;i < N;i++){
        if(P.at(i) < min){
            min = P.at(i);
            wa++;
        }
    }
    cout << wa << endl;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
int MIN(int a,int b){return  abs(a)<abs(b)?a:b;}
int main(){
  int n,m,a,b,s;
  scanf("%d %d",&n,&m);
  s=(n+1)*n/2+(m-1)*n;
  a=m;
  b=m+n-1;
  if(a*b>0)a=MIN(a,b);
  else     a=0;
  printf("%d\n",s-a);
  return 0;
}
  


Measured memory_bytes: 128
flag = 0
N,M,C = map(int,input().split())
B = list(map(int,input().split()))
         
for i in range(N):
         A = list(map(int,input().split()))
         D = [x*y for (x,y) in zip(A,B)]
         if sum(D) + C > 0:
                  flag = flag + 1
print(flag)


Measured memory_bytes: 3060
package main

import (
	"fmt"
)

func main() {
	var S, ans string
	fmt.Scanf("%s", &S)

	switch S {
	case "Sunny":
		ans = "Cloudy"
	case "Cloudy":
		ans = "Rainy"
	case "Rainy":
		ans = "Sunny"
	}

	fmt.Println(ans)
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
signed main(){
    string s;
    int sum=0;
    cin>>s;
    if(s=="RRR"){
        sum=3;
    }else if(s=="RRS" || s=="SRR"){
        sum=2;
    }else if(s=="RSR" || s=="SRS" || s=="SSR" || s=="RSS"){
        sum=1;
    }
    cout<<sum<<"\n";
    return(0);
}

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

int ctoi(char c) {
  if ('0' <= c && c <= '9') return c - '0';
  return -1;
}

int main() {
  string S;
  cin >> S;
  long long K;
  cin >> K;

  char ans = '1';
  for (int i = 0; i < K; i++) {
    if (S.at(i) == '1') {
      continue;
    } else {
      ans = S.at(i);
      break;
    }
  }

  printf("%d", ctoi(ans));
  return 0;
}


Measured memory_bytes: 384
a=int(input())
A = sorted(list(map(int, input().split())))

ans =0
for i in range(a):
  for j in range(i):
    for k in range(j):
      if(A[k] != A[j] and A[i] != A[j] and A[k] + A[j]>A[i]):
        ans+=1

print(ans)

Measured memory_bytes: 9172
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int T;
  cin >> T;
  while(T--){
    int s,d;
    cin >> s >> d;
    int ans = 0;
    for(int i = 0; i < 30; i++){
      if(s&(1<<i)){
        ans++;
        s+=(1<<i);
      }
      if(d&(1<<i)){
        ans++;
        d-=(1<<i);
      }
      if(s==d) break;
    }
    cout << ans << endl;  
  }
  return 0;
}


Measured memory_bytes: 1164
from heapq import heapify,heappop,heappush
n,m = map(int,input().split())
A = list(map(int,input().split()))
heapify(A)
bc = [list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1],reverse=1)

flag = 0
# print(A)
for b,c in bc:
	if flag:
		break
	for i in range(b):
		a = heappop(A)
		if c <= a:
			heappush(A,a)
			flag = 1
			break
		else:
			heappush(A,c)
print(sum(A))

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

int n,k,ans=0;
int a[200005],pre[200005];

map<int,int> m;

signed main()
{
	cin>>n>>k;
	if (k==1)  return cout<<0<<endl,0;
	for (int i=1;i<=n;i++)  cin>>a[i];
	for (int i=1;i<=n;i++)  a[i]--;
	for (int i=1;i<=n;i++)  pre[i]=(pre[i-1]+a[i])%k;

	m[0]=1;
	for (int i=1;i<=n;i++)
	{
		ans+=m[pre[i]];
		m[pre[i]]++;
		if (i>=k-1)  m[pre[i-k+1]]--;
	}
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 19280
def z_algorithm(s):
    n = len(s)
    if(n == 0):
        return []
    if(type(s) is str):
        s2 = [0] * n
        for i, si in enumerate(s):
            s2[i] = ord(si)
        s = s2
    z = [0] * n
    j = 0
    for i in range(1, n):
        z[i] = 0 if (j + z[j] <= i) else min(j + z[j] - i, z[i-j])
        while(i+z[i] < n):
            if(s[z[i]] != s[i + z[i]]):
                break
            z[i] += 1
        if(j + z[j] < i + z[i]):
            j = i
    z[0] = n
    return z

n = int(input())
s = input()

ans = 0
for i in range(n-1):
    si = s[i:]
    z = z_algorithm(si)
    for j,zj in enumerate(z[1:],1):
        ans = max(ans, min(zj, j))
print(ans)

Measured memory_bytes: 80496
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N, P = map(int, input().split())
A = list(map(int, input().split()))
o, e = 0, 0
for i in A:
    if i % 2 == 0:
        e += 1
    else:
        o += 1
ans = 0
for i in range(P, o+1, 2):
    ans += comb(o, i)
print(ans * 2 ** e)


Measured memory_bytes: 62216