akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
const int MOD=1000000007;
const int INF=1000000000;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> P;
vector<int> anscands;
ll N;
ll A[100005];
ll ans=0;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
  std::fill( (T*)array, (T*)(array+N), val );
}
int main(void)
{
  cin >> N;
  ll dp[100005][2];
  Fill(dp,-1);
  dp[0][0]=0;
  for (int i = 1; i <= N; ++i)
    {
      cin >> A[i];
    }
  for (int i = 1; i < N; ++i)
    {
      if(i==1)
	{
	  dp[i][0]=A[i]+A[i+1];
	  dp[i][1]=-1*A[i]+(-1*(A[i+1]));
	}
      else
	{
	  dp[i][0]=max(dp[i-1][0]+A[i+1],dp[i-1][1]+A[i+1]);
	  dp[i][1]=max(dp[i-1][0]+(-2*A[i]+(-1*A[i+1])),dp[i-1][1]+(2*A[i]+(-1*A[i+1])));
	}
    }
  cout << max(dp[N-1][0],dp[N-1][1]) << endl;
}


Measured memory_bytes: 2560
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)
	x := nextInt()
	n := 100

	for i:=1; i<999999999999; i++{
		n = int(float64(n) * 1.01)
		if n >= x {
			fmt.Println(i)
			break
		}
	}
}


Measured memory_bytes: 1756
class SegTree:
    # n : 元の配列の長さ
    # init_list: 元の配列
    # segfunc : 載せる関数（演算）
    # ide_ele : segfuncの単位元
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        #　num : 2**num >= n となる最小の整数 （葉の数）
        # seg : segtreeのリスト
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        # 葉の要素をセット
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        # segtreeの構築
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        #memo: 要素iの子ノードは要素2*i+1, 2*i+2
        #    : 要素iの親ノードは要素(i-1)//2
        
    # 要素の更新 (init_list[k]=x)
    def update(self,k,x):
        k += self.num-1 #葉のノードのインデックス
        self.seg[k] = x
        #末端から頂点まで更新
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])
     
    # 区間クエリ （区間[l,r)に対する演算結果）
    def query(self, l,r):
        if r<=l:
            return self.ide_ele
        
        l += self.num-1 #葉のノードのインデックス
        r += self.num-2 #半開区間から閉区間へ
        ret = self.ide_ele
        
        while r-l>1:
            if l&1 == 0:
                ret = self.segfunc(ret,self.seg[l])
            
            if r&1 == 1:
                ret = self.segfunc(ret,self.seg[r])
                r -= 1
            # 親ノードへ遷移
            l = l//2
            r = (r-1)//2
        if r==l:
            ret = self.segfunc(ret, self.seg[r])
        else:
            ret = self.segfunc(ret, self.seg[l])
            ret = self.segfunc(ret, self.seg[r])
        
        return ret
            
def segfunc(x,y):
    return max(x,y)

def segfunc2(x,y):
    return min(x,y)

def segfunc3(x,y):
    return x | y

def ctoi(c):
    return ord(c) - ord('a')

def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    Segtree = [SegTree(N,[0] * N,segfunc,0) for _ in range(26)]
    for i, c in enumerate(S):
        Segtree[ctoi(c)].update(i,1)

    for _ in range(Q):
        q, *query = map(str, input().split())
        if q == '1':
            i, c = query
            i = int(i) - 1
            if c == S[i]:
                continue
            Segtree[ctoi(c)].update(i, 1)
            Segtree[ctoi(S[i])].update(i,0)
            S[i] = c
        else:
            l, r = query
            l = int(l) - 1
            r = int(r)
            ans = 0
            for j in range(26):
                if Segtree[j].query(l,r):
                    ans += 1
                    
            print(ans)



    


if __name__ == "__main__":
    main()

Measured memory_bytes: 308068
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan = new java.util.Scanner(System.in);
        int n = scan.nextInt();
        int[] a = new int[n - 1];
        int[] out = new int[n];
        for(int i = 0; i < n - 1; i++) {
            a[i] = scan.nextInt();
            out[a[i] - 1]++;
        }
        for(int i = 0; i < n; i++) System.out.println(out[i]);
        scan.close();
    }
}

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

typedef long long ll;
typedef pair<int,int> P;
int dx[] = {-1, 1, 0,  0};
int dy[] = { 0, 0, 1, -1};
 
int main(){
  int n, m, q;
  cin >> n >> m >> q;
  vector<vector<int>> c(n+1, vector<int>(n+1, 0));
  vector<vector<int>> x(n+1, vector<int>(n+1, 0));
  for(int i=0; i<m; i++){
    int l, r;
    cin  >> l >> r;
    x[l][r]++;
  }
  for(int i=1; i<=n; i++){
    for(int j=1; j<=n; j++){
      c[i][j] = c[i][j-1] + x[i][j];
    }
  }
  for(int i=0; i<q; i++){
    int l, r;
    cin >> l >> r;
    int sum = 0;
    for(int j=l; j<=r; j++){
      sum += c[j][r]-c[j][l-1];
    }
    cout << sum << endl;
  }
  return 0;
}


Measured memory_bytes: 2944
MOD = 998244353

N, M, K = map(int, input().split())

fac = [1] * N
for i in range(1, N):
	fac[i] = (fac[i - 1] * i) % MOD

pow_mmm = [1] * N
for i in range(1, N):
	pow_mmm[i] = (pow_mmm[i - 1] * (M - 1)) % MOD

ans = 0
for i in range(K + 1):
	t = (M * pow_mmm[N - 1 - i]) % MOD
	comb = (fac[N - 1] * pow(fac[N - 1 - i], MOD - 2, MOD) * pow(fac[i], MOD - 2, MOD)) % MOD
	t = (t * comb) % MOD
	ans = (ans + t) % MOD
print(ans)

Measured memory_bytes: 79192
n = gets.to_i

a = gets.split.map(&:to_i)

res = Array.new(n) { 0 }

n.times do |i|
  x = n - i
  idx = x - 1

  sum = 0
  j = 2
  while j * x <= n
    idx_j = j * x - 1
    sum += res[idx_j]
    sum %= 2
    j += 1
  end

  res[idx] = a[idx] ^ sum
end

res2 = res.map.with_index{|n, i| [n, i + 1] }.select{ |a| a[0] == 1 }.map{|a| a[1] }
puts res2.count
puts res2.join(' ')

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

/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y) {
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}

int main() {
	int N;
	cin >> N;
	if (N == 1) {
		cout << "Hello World";
	}
	else {
		int a, b;
		cin >> a >> b;
		cout << a + b;
	}
}

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

using namespace std;

#define MAX 100005
#define MAX_N 105

#define int int64_t

int n, w, a[MAX], b[MAX], dp[MAX_N][MAX], be;

int f(int i, int r)
{
    if (r == 0)
        return 0;
    if (r < 0 || i == n)
        return LONG_LONG_MAX / 2;
    if (dp[i][r] != -1)
        return dp[i][r];
    dp[i][r] = min(f(i + 1, r - b[i]) + a[i], f(i + 1, r));
    return dp[i][r];
}

signed main()
{
    scanf("%lld %lld", &n, &w);
    for (int i = 0; i < n; i++)
        scanf("%lld %lld", a + i, b + i);
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= 100002; j++)
            dp[i][j] = -1;
    // printf("%lld %lld\n", n, w);
    for (int j = 100000; j >= 0; j--)
        if (w >= f(0, j))
        {
            printf("%lld\n", j);
            return 0;
        }
    // printf("%lld\n", f(0, w));
}


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

int a[110];
int sum[110];

int main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
	}
	int ans = 0x3f3f3f3f;
	for (int i = 1; i < n; i++){
		ans = min(ans, abs(sum[i] - (sum[n] - sum[i])));
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn=1e5+10;
int n,k,x[maxn],ans=0x7fffffff;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x[i]);
    }
    for(int l=1;l+k-1<=n;l++)
    {
        int r=l+k-1;
        ans=std::min(ans,x[r]-x[l]+std::min(abs(x[l]),abs(x[r])));
    }
    printf("%d\n",ans);
}


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

using namespace std;

typedef long long lli;
typedef long double ld;
typedef pair<lli, lli > plli;
typedef vector<lli> vlli;
typedef vector<plli > vplli;

#define rep(i,a) for(i = 0 ; i < a ; i++)
#define repr(i,a) for(i = a ; i >= 0 ; i--)
#define REP(i,a,b) for(i = a ; i <= b ; i++)
#define REPR(i,a,b) for(i = a ; i >= b ; i--)

#define scan(N) scanf("%lld",&N)
#define print(N) printf("%lld",N)
#define scan2(N1,N2) scanf("%lld %lld",&N1,&N2)
#define print2(N1,N2) printf("%lld %lld",N1,N2)
#define scan3(N1,N2,N3) scanf("%lld %lld %lld",&N1,&N2,&N3)
#define print3(N1,N2,N3) printf("%lld %lld %lld",N1,N2,N3)

#define mem(a,b)memset(a,b,sizeof(a))
#define opt ios_base::sync_with_stdio(false);cin.tie(NULL);
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define sqr(x) (x)*(x)
#define all(a) a.begin(),a.end()
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl

#define endl '\n'

const long long INF = 2000000000000;
const long long MOD = 1000000007;
const long long MAXN = 100005;

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

lli power(lli a,lli b)
{
    lli value;
    if(!b)
    	return 1;
    else if(b%2==0) {
        value = power(a,b/2)%MOD;
        return (value * value)%MOD;
    }
    else {
        value = power(a,b/2)%MOD;
        return ((a*value)%MOD*(value))%MOD;
    }
}

bool f(lli x)
{
    string s = to_string(x);
    lli i,n = s.length();
    rep(i,n/2)
    {
        if(s[i] != s[n-1-i])
            return false;
    }
    return true;
}
int main()
{
	opt;
    lli a,b;
    cin >> a >> b;
    lli i,ans = 0;
    REP(i,a,b)
    {
        if(f(i))
            ans++;
    }
    cout << ans ;
	return 0;
}










Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n-1);i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(std::unique(all(x)), x.end());
typedef long long ll;
const int INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;
const double PI=acos(-1);
using namespace std;
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; }
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

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

    if(d==0) {
        cout<<(x==0 ? 1 : n+1)<<endl;
        return 0;
    }

    map<ll, vector<pair<ll,ll>>> mp;
    for(ll k = 0; k <= n; k++) {
        ll l=k*(k-1)/2;
        ll r=k*(2*n-k-1)/2;
        ll c=k*x+d*l;

        mp[(c+d*INF)%d].emplace_back((c-(c+d*INF)%d)/d,1);
        mp[(c+d*INF)%d].emplace_back((c-(c+d*INF)%d)/d+r-l+1,-1);
    }

    ll ans=0;
    for(auto vv:mp) {
        auto ev=vv.second;
        sort(all(ev));
        ll cnt=0,pre=-LINF;
        for(auto p:ev) {
            if(cnt>0) ans+=p.first-pre;
            cnt+=p.second;
            pre=p.first;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 25216
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long; 
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
//constexpr long long MOD = 998244353LL;
template<class T, class U> inline bool chmax(T &a, U b) { if (a < b) { a = b; return true;} return false; }
template<class T, class U> inline bool chmin(T &a, U b) { if (a > b) { a = b; return true;} return false; }
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int a1, a2, a3; cin >> a1 >> a2 >> a3;
    string ans;
    
    if((a1 + a2 + a3) >= 22) ans = "bust";
    else ans = "win";

    cout << ans << ln;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll                  long long
#define dl                 long double
#define pb                push_back
#define F                  first
#define S                  second
#define endl              "\n"
#define rep(i,a,b)       for(i=a;i<b;i++)
#define all(v)             v.begin(),v.end()
#define allr(v)            v.rbegin(),v.rend()
#define mod              1000000007LL
#define CIN(V,s,n)      for(int i=s;i<n;i++){cin >> V[i];}
#define COUT(V,s,n)   {for(int i=s;i<n;i++){cout <<  V[i] << " "  ;} cout << endl;}
#define fast               ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define CLEAR(V);      for(ll i=0;i<V.size();i++) V[i] = 0;
#define N                  101LL
#define tmod             998244353LL
using namespace std;

bool sBs(const pair<int,int> &a,const pair<int,int> &b)
{   return (a.second < b.second);   }

ll SUMD(ll n);
ll BS(vector<pair< ll ,ll > > &PS,ll s,ll e,ll ser);
ll MI(ll a, ll m);
ll P[N+1];
void Sieve(int n=N);
ll Powb(ll b,ll n,ll m);

bool check(int m,vector<ll> &A,int n)
{
    for(int i=0;i<=n-m;i++)
    {
        if(A[i]!=A[i+m] ) return true;
    }
    return false;
}

int main()
{
fast;
ll q=1,t;
//cin >> q; t = q;
while(q--)
{
    ll i,j,n,m,k,l,r,a=0,b=0,c=0,d=0,e,g=1,p,u,v,w,x,y,flag=0;
    //n=m=k=i=j=l=r=a=b=c=d=u=v=w=p=x=y=0;
    for(i=1;i<=5;i++)
    {
        cin >> u;
         if(u==0)
         {
             cout << i;
             return 0;
         }
    }
}
    return 0;
}

//*****************************************************************************************************************************************

ll Powb(ll b,ll n,ll m)
{
    if(n==0) return 1LL;
    if(n==1) return b;
    ll temp = Powb(b,n/2,m);
    if(n%2==0){return (temp*temp)%m;}
    else{return (b*((temp*temp)%m))%m;}
}

ll SUMD(ll n)
{   ll sum=0;
    while(n>0){sum += n%10;n = n/10;}
    return sum;

}
ll BS(vector<pair<ll,ll> > &PS,ll s,ll e,ll ser)
{
    if(s>e)
        return s;
    ll mid = (s+e)/2;
    if(PS[mid].F==ser)
    {
        return mid;
    }
    else if(PS[mid].F > ser)
    {
        return BS(PS,s,mid-1,ser);
    }
    else
        return BS(PS,mid+1,e,ser);
}
ll MI(ll a, ll m)
{
    ll m0 = m;
    ll y = 0, x = 1;
    if (m == 1)
      return 0;
    while (a > 1)
    {
        ll q = a / m;
        ll t = m;
        m = a % m, a = t;
        t = y;
        y = x - q * y;
        x = t;
    }
    if (x < 0)
       x += m0;
    return x;
}

void Sieve(int n)
{
    //memset(P,true,sizeof(P));
    //P[0] = false;
    //P[1]= false;
    for(int i=1;i<=n;i++) P[i] = i;
    for(ll i=2;i*i<=n;i++)
    {
        if(P[i]==i)
        {
            for(ll j=i*i;j<=n;j+=i)
            {
                if(P[j]==j)
                    P[j]=i;
            }
        }
    }

}



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

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int count = 0;
	for (int i = 0; i < 3; i++) {
		int x;
		cin >> x;
		if (x == 5) count += 5;
		if (x == 7) count += 7;
	}
	
	count == 17 ? cout << "YES" : cout << "NO";
}


Measured memory_bytes: 256
#pragma target("avx")
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using V = std::vector<ll>;
template<typename T> using pq = std::priority_queue<T>;
template<typename T> using rpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define rep(i,b,e) for(ll i=b; i<e; i++)
#define be(vec) vec.begin(),vec.end()
#define print(vec) printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");
#define scan(vec) for(auto &i:vec)scanf("%ld",&i)
#define fi first
#define se second

const int MOD = 1e9+7;
const ll INF = 1e18;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

int main(){
	int n, m, x;
	scanf("%d %d %d", &n, &m, &x);
	V a(m); scan(a);
	int idx = std::lower_bound(be(a), x) - a.begin();
	printf("%d\n", std::min(idx, m-idx));
	return 0;
}


Measured memory_bytes: 256
program main
integer,allocatable :: a(:),b(:)
integer :: n,i,ans
read *,n
allocate(a(n),b(n-1))
read *,b

ans = b(1)
do i = 2,n-1
if (b(i)<b(i-1)) then
ans = ans + b(i)
else 
ans = ans + b(i-1)
end if
end do
ans = ans + b(n-1)

print *,ans
end program main

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

using namespace std;
#define int long long
map<int,int> row,col;
vector<int> a,b;
map<pair<int,int>,int> mp;
signed main(){
	int n,m,k;
	cin>>n>>m>>k;
	int maxn_row=-1,maxn_col=-1;
	for(int i=0;i<k;i++){
		int x,y;
		cin>>x>>y;
		row[x]++,col[y]++;
		maxn_row=max(maxn_row,row[x]);
		maxn_col=max(maxn_col,col[y]);
		mp[make_pair(x,y)]=1;
	}
	for(int i=1;i<=n;i++) if(maxn_row==row[i]) a.push_back(i);
	for(int i=1;i<=m;i++) if(maxn_col==col[i]) b.push_back(i);
	int maxn=0;
	sort(a.begin(),a.end(),greater<int>()),sort(b.begin(),b.end(),greater<int>());

	for(int i=0;i<a.size();i++){
		for(int j=0;j<b.size();j++){
			if(!mp[make_pair(a[i],b[j])]){
				cout<<max(maxn,row[a[i]]+col[b[j]]);return 0;
			}else{
				maxn=max(maxn,row[a[i]]+col[b[j]]-1);
			}
		}
	}
	cout<<maxn;
	return 0;
} 

Measured memory_bytes: 67764
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n=int(input())
    # 文字列を一文字ずつのリストにして、辞書順にソートしたあと、文字列に戻す
    # ['aab','aab','aab','ccd','ccd']ってなってる
    l=[''.join(sorted(list(input()))) for i in range(n)]

    from collections import Counter
    c=Counter(l)# ()にカウンターの対象のリストの変数名
    # print(c)するとCounter({'aab': 3, 'ｃｃｄ': 2})ってなってる
    # print(c.values())すると[3,2]
    ans=0
    for j in c.values():
        ans+=(j*(j-1))//2
    print(ans)
resolve()

Measured memory_bytes: 19760
/* 実行時間1s制限の場合
  10^6 1,000,000   : 余裕をもって間に合う
  10^7 10,000,000  : おそらく間に合う
  10^8 100,000,000 : 非常にシンプルな処理でないと厳しい
 */
#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)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll; // long longはデータモデル(LLP64, LP64, ...)によらず64bit.
ll gcd(ll a, ll b) {return b ? gcd(b, a%b) : a;}  // Greatest Common Divisor ユークリッドの互除法（aが長辺）
vector<pair<ll,int>> factorize(ll n) {            // a,bの公約数 = GCD(a, b)の約数
    vector<pair<ll,int>> res;
    for (ll i = 2; i*i <= n; i++) { // √nまで探せばよい
        if (n%i) continue;
        res.emplace_back(i, 0);     // 割り切れたら
        while (n%i == 0) {
            n /= i;
            res.back().second++;
        }
    }
    if (n != 1) res.emplace_back(n, 1); // この時点で1でなかったら、残りは素数.
    return res;
}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}         // Least Commont Multiple オーバーフローしないように先に割る
ll ceil(ll a, ll b) {return (a+b-1)/b;}

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

int main(int argc, char* argv[])
{
#ifdef LOCAL
    // 以降 cin の入力元が 'xxx.txt' になる
    // std::ifstream in(argv[1]);
    //std::cin.rdbuf(in.rdbuf());
    std::ifstream in("a.txt");
    std::cin.rdbuf(in.rdbuf());
#endif

    int H, W, h, w;
    cin >> H >> W;
    cin >> h >> w;

    cout << H*W - (h * W + w * H - h * w);

    return 0;
}

/*
  - 1e9 : 10^9
  - container一般
    - 合計
      accumulate(a.begin(), a.end(), 0LL)  0LLはオーバーフロー用
  - vector
    vector<int> A(N, 0); // 0で初期化(省略可)
    - loop
      for  (int i = 0; i < A.size(); i++) {}
      for  (int elem : A) {}
    - sort
      std::sort(v.begin(), v.end());  // 昇順
      std::sort(v.begin(), v.end(), std::greater<int>()); //降順
      - vector<vector<int>> cnt(h, vector<int>(w))
    - sort(struct)
        struct st_t {
            string name;
            int p;
            bool operator<(const st_t& another) const {
                if (name == another.name)
                {
                    return p > another.p;
                }
                return name < another.name;
            }
        };
        vector<st_t> st(n);
        sort(st.begin(), st.end());
  - pair
    - pairのソートの定義 : firstが優先的に比較。同じだったらsecond。
    - pair<pair<string,int>,int> p[110];
      std::sort(p,p+a);
        こうすると、first.first -> first.second -> secondの順にソートされる
    - sort
      - sort(a.begin(), cb.end(), greater<pair<int, int>>());
  - map
    - for (auto x : map) {}  // x.first:key  x.second:value.
  - priority_queue<int> q;
    - q.top()に最大値が入っている
  - string
    - loop
      for (char& c : s) {}
 */



Measured memory_bytes: 256
from itertools import product


def read_input():
    n = int(input())
    testimonies = {}

    for i in range(n):
        testimonies[i] = []
        a = int(input())
        for _ in range(a):
            x, y = map(int, input().split())
            testimonies[i].append((x - 1, y))

    return n, testimonies


def contradict(pattern, testimonies):
    for i, p in enumerate(pattern):
        if not p:
            continue
        else:
            for x, y in testimonies[i]:
                if pattern[x] != int(y):
                    return True    
    return False
            


def submit():
    n, testimonies = read_input()

    for pattern in product([True, False], repeat=n):
        if not contradict(pattern, testimonies):
            print(sum(pattern))
            break


if __name__ == "__main__":
    submit()

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int x;
    int count=0;
    for(int i=0;i<n;i++){
        if(i==0){x=1;}
        x=a[x-1];
        if(x==2){cout<<i+1<<endl; break;}
        else{count++;}
    }
    if(count==n){cout<<-1<<endl;}
    return 0;
}

Measured memory_bytes: 640
/*
读题不规范，爆零两行泪。
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
	long long a,b,c;
	cin>>a>>b>>c;
	if(b-1>c)cout<<int(a*(1.*c/b));
	else cout<<int(a*(1.*(b-1)/b));
	return 0;
}

Measured memory_bytes: 3472
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long a = Long.parseLong(sc.next());
        long b = Long.parseLong(sc.next());
        long c = Long.parseLong(sc.next());
        long d = Long.parseLong(sc.next());
        long max = Long.MIN_VALUE;
        if(a - b != 0){
            if(a == 0) a += 1;
            if(b == 0) b -= 1;
        }
        if(c - d != 0){
            if(c == 0) c += 1;
            if(d == 0) d -= 1;
        }
        max = Math.max(max, a * c);
        max = Math.max(max, a * d);
        max = Math.max(max, b * c);
        max = Math.max(max, b * d);
        System.out.println(max);
    }
}


Measured memory_bytes: 35636
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main(){
    string X;
    cin >> X;
    vector<long long> ct(2, 0);
    long long ans = X.size();
    for(int i = 0; i < X.size(); i++){
        if(X[i] == 'S') ct[0]++;
        else if(X[i] == 'T') ct[1]++;
        if(i >= 1){
            if(X[i] == 'S' && X[i - 1] == 'T'){
                ans -= min(ct[0] - 1, ct[1])*2;
                if(ct[0] - 1 > ct[1]) ct[0] = ct[0] - ct[1];
                else ct[0] = 1;
                ct[1] = 0;
            }
        }
    }
    if(X[X.size() - 1] == 'T'){
        ans -= min(ct[0], ct[1])*2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)

int main() {
  int N;
  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];
  int ans = 0;
  for (int i = 0; i < N; i++) {
    if (V[i] > C[i]) ans += V[i] - C[i];
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n , m;
	cin>>n>>m;
	char a[n][m];	
	for(int i =0 ; i < n ;i ++)
	{
		for(int j = 0 ; j < m ; j ++)
		{
			cin>>a[i][j];
		}
	}
	for(int i = 0 ; i < n- 1;i ++)
	{
		for(int j =0 ; j < m - 1 ;j ++)
		{
			if(a[i][j + 1] == '#' &&a[i + 1][j] == '#' )
			{
				cout<<"Impossible";
				return 0;
			}
		}
	}cout<<"Possible";
}

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

#define INF 2147483647
#define LINF 9223372036854775807
#define MOD 1000000007
#define MOD2 998244353

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

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define se second
#define fi first

typedef long long ll;
typedef long double ld;

typedef pair<int,int> P;
typedef pair<int,P> iP;
typedef pair<P,P> PP;

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

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





int main(){

    bool flag=false;
    ll ans=0,sum=0;

    int n;
    cin>>n;

    int Allxor = 0;

    vector<int> a(n);
    rep(i,n){
        cin>>a[i];
        Allxor ^= a[i];
    }

    rep(i,n){
        cout<<(Allxor^a[i]);
        if(i!=n-1)cout<<" ";
    }

    //cout <<fixed<<setprecision(16)<< << endl;
    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    return 0;
}


Measured memory_bytes: 3944
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++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(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<long double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    int n;
    cin >> n;
    VL a(n), b(n);
    REP(i,n) a[i] = in();
    REP(i,n) b[i] = in();
    REP(i,n){
        if (a[i] > b[i]){
            cout << -1 << endl;
            return 0;
        }
    }
    queue<int> que;
    REP(i,n){
        ll x = b[(i+1)%n], y = b[(i+n-1)%n];
        if (b[i] > x + y) que.push(i);
    }
    ll ans = 0;
    while (!que.empty()){
        int i = que.front();
        que.pop();
        ll x = b[(i+1)%n], y = b[(i+n-1)%n], s = x + y;
        ll c1 = (b[i] - max(x, y)) / s + 1;
        ll c2 = (b[i] - a[i]) / s;
        // cout << c1 << " " << c2 << endl;
        ll c = min(c1, c2);
        ans += c;
        b[i] -= c * s;
        // cout << i << " " << c << endl;
        // REP(j,n) cout << b[j] << " ";
        // cout << endl;
        if (x > b[i] + b[(i+2)%n]) que.push((i+1)%n);
        if (y > b[i] + b[(i+n-2)%n]) que.push((i+n-1)%n);
    }
    REP(i,n){
        if (a[i] != b[i]){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define repr(i, a, b) for(ll i = (a); i < (b); i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
const ll MOD = 1000000007;
const ll INF = 100000000000000000LL;
inline ll GCD(ll a, ll b){ return b?GCD(b, a % b):a; }
inline ll LCM(ll a, ll b){ return a/GCD(a, b)*b; }
inline ll powint(ll x, ll y){ ll r=1; while(y){ if(y&1) r*=x; x*=x; y>>=1; } return r; }
inline ll powmod(ll x, ll y, ll m = MOD){ ll r=1; while(y){ if(y&1) r*=x; x*=x; r%=m; x%=m; y>>=1; } return r; }
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; }
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n;
    cin >> n;
    vll a(n);
    rep(i, n){
        cin >> a[i];
    }
    vll b(n);
    rep(i, n){
        cin >> b[i];
    }
    if(accumulate(ALL(a), 0LL) < accumulate(ALL(b), 0LL)){
        cout << -1 << endl;
        return 0;
    }
    vll c(n);
    ll debt = 0;
    ll ans = 0;
    rep(i, n){
        c[i] = a[i] - b[i];
        if(c[i] < 0){
            debt -= c[i];
            ans++;
        }
    }
    if(ans == 0){
        cout << 0 << endl;
        return 0;
    }
    sort(ALL(c));
    reverse(ALL(c));
    rep(i, n){
        debt -= c[i];
        ans++;
        if(debt <= 0) break;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
N = int(input())
d = {i+1: [] for i in range(N)}
for i in range(N-1):
    u, v, w = map(int, input().split())
    d[u].append([v, w])
    d[v].append([u, w])

dist = {i+1: -1 for i in range(N)}
stack = [1]
dist[1] = 0

while len(stack) != 0:
    prev = stack.pop()
    prev_d = dist[prev]
    for v, w in d[prev]:
        if dist[v] == -1:
            stack.append(v)
            dist[v] = prev_d + w

for i in range(N):
    if dist[i+1] % 2:
        print('1')
    else:
        print('0')


Measured memory_bytes: 66944
fun main(args: Array<String>) {
    val s = readLine()!!
    val x1 = s.take(2).toInt()
    val x2 = s.takeLast(2).toInt()

    val ans = when {
        x1 in 1..12 && x2 in 1..12 -> "AMBIGUOUS"
        x1 !in 1..12 && x2 in 1..12 -> "YYMM"
        x1 in 1..12 && x2 !in 1..12 -> "MMYY"
        else -> "NA"
    }

    println(ans)
}


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

using namespace std;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

typedef pair<ll, ll> P;

#define bit(n) (1LL << (n))

//#define int long long

#define all(v) v.begin(), v.end()
#define sortAl(v) sort(all(v))
#define sortAlr(v)          \
  sort(v.begin(), v.end()); \
  reverse(v.begin(), v.end())

#define rep(i, n) for (ll i = 0; i < n; i++)
#define REP(i, n) for (ll i = 1; i < n; i++)

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)

template <class T>
inline void chmax(T &a, T b) {
  a = std::max(a, b);
}
template <class T>
inline void chmin(T &a, T b) {
  a = std::min(a, b);
}

#define mod (ll)(1e9 + 7)
#define INF LLONG_MAX

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);

  string s;
  cin >> s;

  ll n = s.size();

  vvll dp(4, vll(n + 1));

  dp[0][0] = 1;

  rep(i, n) {
    // 1こ前のdpを引き継ぎ
    rep(j, 4) {
      // ? なら3倍に
      if (s[i] == '?') {
        dp[j][i + 1] = dp[j][i] * 3;
      } else {
        dp[j][i + 1] = dp[j][i];
      }
    }

    rep(j, 3) {
      if (s[i] == 'A' + j || s[i] == '?') {
        dp[j + 1][i + 1] += dp[j][i];
      }
    }

    rep(j, 4) {
      dp[j][i + 1] %= mod;
    }
  }

  cout << dp[3][n] << endl;

  return 0;
}


Measured memory_bytes: 4432
"use strict";
const Main = (input) =>{
   let xs = input.trim().split('\n');
   let N = Number(xs[0]);
   let S = xs[1].split('');
   let ans = 0;
   for(let i=0; i<=N-3; i++){
   	if(S[i]+S[i+1]+S[i+2]=='ABC'){
   	  ans++
    }
   }
   console.log(ans);

}
Main(require('fs').readFileSync('/dev/stdin','utf8'));

Measured memory_bytes: 21064
#include<bits/stdc++.h>
const int N=5e5+5,mo=998244353;
int vf[N],fac[N],inv[N],n,m,i,ans,m1[N],m2[N];
inline int C(int n,int m){return 1ll*vf[m]*vf[n-m]%mo*fac[n]%mo;}
int main(){
	for(i=*vf=*fac=1;i<N;++i)inv[i]=i==1?1:1ll*(mo-mo/i)*inv[mo%i]%mo,
		vf[i]=1ll*vf[i-1]*inv[i]%mo,fac[i]=1ll*fac[i-1]*i%mo;
	scanf("%d%d",&n,&m);
	for(i=*m1=*m2=1;i<N;++i)m1[i]=1ll*m1[i-1]*(m+1)%mo,m2[i]=1ll*m2[i-1]*(n+1)%mo;
	for(i=std::max(n-m,0);i<=n;++i)
		ans=(ans+1ll*C(n,i)*vf[m-n+i]%mo*m1[i]%mo*((n-i)&1?mo-m2[m-n+i]:m2[m-n+i]))%mo;
	ans=1ll*ans*fac[m]%mo;printf("%d\n",ans);	
	return 0;
}

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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

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

int N;
char s[333][333];
int i,j,k,ans;
int main(){
    scanf("%lld", &N);
    fornum(i,0,N){
        scanf("%s", s[i]);
    }
    fornum(i,0,N){
        int flag = 1;
        fornum(j,0,N){
            fornum(k,0,N){
                if(s[(j+i)%N][k]!=s[(k+i)%N][j]){
                    flag = 0;
                }
            }
        }
        if(flag){
            ans += N;
        }
    }
    printf("%d", ans);

    return 0;
}

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

signed main(){
	int ans = 700;
	string s;
	cin >> s;
	for(int i = 0;i < 3;i++) {
		if(s[i] == 'o') ans += 100;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;

ll N;
map<ll,ll> mp;
int main(){
    cin>>N;
    for(ll i=0;i<N;i++){
        ll a;
        cin>>a;
        mp[a]++;
    }
    ll cnt=0;
    for(auto p:mp){
        if(p.second>1){
            cnt+=p.second-1;
        }
    }
    cout<<N-(cnt+1)/2*2<<endl;
    return 0;
}

Measured memory_bytes: 6528
n,m = map(int, input().split())
a = list(map(int, input().split()))
cb = [list(map(int,input().split()))[::-1] for _ in range(m) ]
cb.append([-1,1])

a.sort()
cb.sort()

i= n-1
j = m

ans = 0
remain = n
while(remain > 0):
    if( a[i] > cb[j][0] ):
        ans += a[i]
        i -= 1
        remain -= 1
    else:
        ans += cb[j][0] * min(remain, cb[j][1])
        remain -= cb[j][1]
        j -= 1

print(ans)

Measured memory_bytes: 76184
#include <bits/stdc++.h>
#include<math.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)


int main() {
  int N;
  cin>>N; 
  
    cout<<N/3<<endl;
  
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		if (a > b)
			System.out.println("a > b");
		else if (a < b)
			System.out.println("a < b");
		else {
			System.out.println("a == b");
		}
		sc.close();
	}
}

Measured memory_bytes: 26312
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

/*
0に近い方から左右に交互に振り分けるのが最適
よく見る形
*/

ll n,ans=99,l=0,r=0;
map<ll,ll> m;

void init(){
	cin>>n;
	rep(i,n){
		ll d;
		cin>>d;
		m[d]++;
	}
}

int main(void){
	init();
	if(m[0]>0)ans=0;
	reg(i,1,11){
		if(m[i]>2){
			ans=0;
		}
		if(m[i]==2){
			ans=min({ans,i-l,i-r,24-2*i});
			l=i;
			r=i;
		}
		if(m[i]==1){
			if(l<r){
				ans=min({ans,i-l,24-i-r});
				l=i;
			}else{
				ans=min({ans,i-r,24-i-l});
				r=i;
			}
		}
	}
	if(m[12]==1)ans=min({ans,12-l,12-r});
	if(m[12]==2)ans=0;
	cout<<ans<<endl;
	return 0;
}

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

using namespace std;

#define int long long 
#define INF 1e9
#define LINF 1e18

typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<int, P> Pi;
typedef pair<P, P> PP;

const int MOD = 1e9 + 7;
const int dy[] = { 0, 0, 1, -1 };
const int dx[] = { 1, -1, 0, 0 };

template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

int C, N;
string s[1001];
bool flag[500][500];

bool check(int y, int x) {
    return (s[y][x] == s[N - y - 1][x] && s[y][x] == s[y][N - x - 1] && s[y][x] == s[N - y - 1][N - x - 1]);
}

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

    cin >> C >> N;
    for(int i  = 0; i < N; ++i) cin >> s[i];
    int res = 0, cnt = 0;
    for(int i = 0; i < N / 2; ++i) {
        for(int j = 0; j < N / 2; ++j) {
            if(!check(i, j)) ++cnt;
            else flag[i][j] = true;
        }
    }
    if(cnt == 0) ++res;
    for(int i = 0; i < C - 1; ++i) {
        int d;
        cin >> d;
        for(int j = 0; j < d; ++j) {
            int y, x;
            cin >> y >> x;
            --y; --x;
            s[y][x] = (s[y][x] == '0') ? '1' : '0';
            if(y >= N / 2) y = N - y - 1;
            if(x >= N / 2) x = N - x - 1;
            if(check(y, x) && !flag[y][x]) {
                flag[y][x] = true;
                --cnt;
            }
            else if(!check(y, x) && flag[y][x]) {
                flag[y][x] = false;
                ++cnt;
            }
        }
        if(cnt == 0) ++res;
    }
    cout << res << endl;
    return 0;
}



Measured memory_bytes: 4408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[200005], b[200005];
ll sum[200005];
int main(){
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for(int i=1;i<=n;i++) scanf("%d", &a[i]), sum[i] = sum[i-1] + a[i];
    for(int i=1;i<=m;i++) scanf("%d", &b[i]);
    int ans = 0;
    ll cnt = 0;
    for(int i=0;i<=m;i++){
        cnt += b[i];
        if(cnt > k) break;
        int lo = 0, hi = n, res = 0;
        while(lo <= hi){
            int mid = (lo+hi)/2;
            if(sum[mid] + cnt <= k) res = mid, lo = mid+1;
            else hi = mid-1;
        }
        ans = max(ans, i+res);
        if(cnt > k) break;
    }
    printf("%d\n", ans);
}

Measured memory_bytes: 6936
/* Simplicity and Goodness */
 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
using namespace std;
// typedef tree<int, null_type, less<int>, rb_tree_tag,
//             tree_order_statistics_node_update> indexed_set;

void my_dbg() { cout << endl; }
template<typename Arg, typename... Args> void my_dbg(Arg A, Args... B) 
{ cout << ' ' << A; my_dbg(B...); }
#define dbg(...)  cout << "(" << #__VA_ARGS__ << "):", my_dbg(__VA_ARGS__)

#define scn(n) scanf("%d", &n)
#define lscn(n) scanf("%lld", &n)
#define pri(n) printf("%d ", (int)(n))
#define prin(n) printf("%d\n", (int)(n))
#define lpri(n) printf("%lld ", n)
#define lprin(n) printf("%lld\n", n)
#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;

const int inf = INT_MAX;
const int ninf = INT_MIN;
const int mod = 1e9+7;
const int N = 2e5+2;

char a[22][22];
int dist[22][22], vis[22][22];

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

int bfs(int i, int j, int n, int m)
{
    memset(vis, 0, sizeof(vis));
    queue<pair<int, int>> q;
    q.emplace(i, j);
    int mx = 0;
    dist[i][j] = 0; vis[i][j] = 1;

    while(!q.empty())
    {
        int x = q.front().F;
        int y = q.front().S;
        q.pop();

        rep(k, 0, 4) {
            int nx = x + dx[k], ny = y + dy[k];

            if(nx < 1 || nx > n || ny < 1 || ny > m || a[nx][ny] == '#')
                continue;

            if(!vis[nx][ny]) {
                vis[nx][ny] = 1;
                dist[nx][ny] = 1 + dist[x][y];
                mx = max(mx, dist[nx][ny]);
                q.emplace(nx, ny);
            }
        }
    }

    return mx; 
}

void solve()
{
    int n, m;
    scn(n); scn(m);

    int mx = 0;

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++)
            cin >> a[i][j];
    }

    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(a[i][j] == '.') {
                mx = max(mx, bfs(i, j, n, m));
            }
        }
    }

    prin(mx);
}

int main()
{
    int t = 1;
    // scn(t);

    while(t --) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3680
nk = list(map(int, input().split()))
n = int(nk[0])
k = int(nk[1])
s = list(input())

ans = 0
l = 0
r = 0

for i in range(n-1):
    if s[i] == s[i+1]:
        ans += 1
    elif s[i] == ('R'):
        r += 1
    else :
        l += 1

ans += min(k,max(l,r)) + min(k,l,r)

print(ans)

Measured memory_bytes: 4084
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

int main() {
    lint n;
    cin >> n;

    double odd = 0;
    for(lint i=1; i<=n; i++) {
        if(i % 2 == 1)  odd++;
    }

    cout << fixed << setprecision(10) << odd / n << endl;
}

Measured memory_bytes: 256
import sys
def input(): return sys.stdin.readline().rstrip()
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n # 親(uf.find()で経路圧縮して根)の番号。根の場合は-(そのグループの要素数)
    def find(self,x):
        #グループの根を返す
        if self.parents[x]<0:return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        #要素x,yのグループを併合
        x,y=self.find(x),self.find(y)
        if x==y:return
        if self.parents[x]>self.parents[y]:#要素数の大きい方をxに
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x #要素数が大きい方に併合
    def roots(self):
        #全ての根の要素のリスト
        return [i for i, x in enumerate(self.parents) if x<0]
    def group_count(self):
        #グループの数
        return len(self.roots())

def main():
    n,m=map(int,input().split())
    uf=UnionFind(n)
    XYZ=[tuple(map(int,input().split())) for i in range(m)]
    for x,y,_ in XYZ:
        uf.unite(x-1,y-1)
    print(uf.group_count())


if __name__=='__main__':
    main()

Measured memory_bytes: 22128
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,a,b) for(int i=a;i<b;i++)
#define each(it,v) for(auto it : v)
#define mod 1000000007
#define all(v) (v).begin(),(v).end()
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pair<int,int>>
#define vv vector<vector<int>>
using namespace std;

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

    bool f=true;

    vpii v;
    int a,b;
    rep(i,n)
    {
        cin>>a>>b;
        v.push_back(make_pair(b,a));
    }

    sort(all(v));

    int time=0;
    rep(i,n)
    {
        time+=v[i].second;
        if(time>v[i].first)f=false;
    }
    if(f)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N; cin>>N;
    int t[N+1],x[N+1],y[N+1];
    t[0]=0;x[0]=0;y[0]=0;
    for(int i=0;i<N;i++){
        cin>>t[i+1]>>x[i+1]>>y[i+1];
        int dt=t[i+1]-t[i];
        int dx=x[i+1]-x[i];
        int dy=y[i+1]-y[i];
        if(dt>=(abs(dx)+abs(dy))&&(dt%2==((abs(dx)+abs(dy))%2))){
            continue;
        }
        else{
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
using namespace std;

#define N  100005

void solve()
{
	ll a,b;
	cin>>a>>b;
	if(a==1 or b==1){
		cout<<1;
		return;
	}
	ll x=(b+1)/2;
	ll y=b/2;
	ll z=(a+1)/2;
	ll w=a/2;
	cout<<x*z+y*w;	
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
	while(TESTS--)
	{
		solve();
	}
	return 0;
}

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back

bool hantei(int x, int y, int z, int Y) {
  if(x*10000 + y*5000 + z*1000 == Y) return true;
  return false;
}

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

  int N, Y;
  cin >> N >> Y;

  rep(x, N + 1) {
    rep(y, N + 1) {
      if((Y - x*10000 - y*5000) % 1000 != 0) continue;
      if((Y - x*10000 - y*5000) < 0) continue;
      int z = (Y - x*10000 - y*5000) / 1000;
      if(x + y + z != N) continue;
      if(hantei(x, y, z, Y)) {
        cout << x << " " << y << " " << z << endl;
        return 0;
      }
    }
  }

  cout << "-1 -1 -1" << endl;
  return 0;
}


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

using std::cin;
using std::cout;
using std::cerr;

using std::abs;
using std::min;
using std::max;
using std::swap;

using std::map;
using std::pair;
using std::set;
using std::string;
using std::vector;

using std::sort;
using std::reverse;

using ll = long long;

#define forn(i, n) for (ll i = 0; i < (ll) n; ++i)
#define sz(a) static_cast<int>(a.size())
#define endl '\n'

struct __init {
    __init() {
        cin.tie(nullptr);
        std::iostream::sync_with_stdio(false);
        cout << std::fixed << std::setprecision(10);
        cerr << std::fixed << std::setprecision(5);
        std::mt19937 rand(300);
    }

    ~__init() {
        #ifdef SEREZHKA
            cerr << "Time elapsed: " << static_cast<double>(clock()) / CLOCKS_PER_SEC << endl;
        #endif
    }
} init;

const ll inf = (ll) 1e9 + 7ll;
const int maxn = (int) 1e6 + 17;

int n;
int a[maxn];

bool read() {
    if (!(cin >> n))
        return false;

    forn (i, n)
        cin >> a[i];

    return true;
}

void solve() {
    std::bitset<2000 * 2000 + 1> dp;
    dp[0] = 1;

    forn (i, n)
        dp |= (dp << a[i]);

    int S = std::accumulate(a, a + n, 0);

    for (int k = (S + 1) / 2; k <= 2000 * 2000; ++k)
        if (dp[k]) {
            cout << k << endl;
            return ;
        }
}

int main() {
#if SEREZHKA
    freopen("file.in", "r", stdin);
#endif

    while (read())
        solve();

    return 0;
}


Measured memory_bytes: 1920