akhauriyash/Code-Regression huggingface dataset:
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=1e9;
const ll INF=5e18;
typedef pair<int,int> P;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  string s;
  int n,q,a[100005]={},l,r;
  cin >> n >> q >> s;
  for(int i=0; i<n-1; i++) {
    if(s[i]=='A'&&s[i+1]=='C') {
      a[i+2]=1;
    }
  }
  for(int i=1; i<=n; i++) {
    a[i]+=a[i-1];
  }
  while(q--) {
    cin >> l >> r;
    cout << a[r]-a[l] << endl;
  }
}

Measured memory_bytes: 1488
def main():
    H = map(int, open(0).read().split()[:1:-1])
    pre = None
    for h in H:
        if pre is None:
            pre = h
        elif h <= pre:
            pre = h
        elif pre + 1 == h:
            continue
        else:
            # pre + 1 < h
            print("No")
            return

    print("Yes")
    return


main()


Measured memory_bytes: 11200
macro_rules !input {(source =$s :expr ,$($r :tt ) *) =>{let mut iter =$s .split_whitespace () ;let mut next =||{iter .next () .unwrap () } ;input_inner !{next ,$($r ) *} } ;($($r :tt ) *) =>{let stdin =std ::io ::stdin () ;let mut bytes =std ::io ::Read ::bytes (std ::io ::BufReader ::new (stdin .lock () ) ) ;let mut next =move ||->String {bytes .by_ref () .map (|r |r .unwrap () as char ) .skip_while (|c |c .is_whitespace () ) .take_while (|c |!c .is_whitespace () ) .collect () } ;input_inner !{next ,$($r ) *} } ;}
macro_rules !input_inner {($next :expr ) =>{} ;($next :expr ,) =>{} ;($next :expr ,$var :ident :$t :tt $($r :tt ) *) =>{let $var =read_value !($next ,$t ) ;input_inner !{$next $($r ) *} } ;}
macro_rules !read_value {($next :expr ,($($t :tt ) ,*) ) =>{($(read_value !($next ,$t ) ) ,*) } ;($next :expr ,[$t :tt ;$len :expr ] ) =>{(0 ..$len ) .map (|_ |read_value !($next ,$t ) ) .collect ::<Vec <_ >>() } ;($next :expr ,chars ) =>{read_value !($next ,String ) .chars () .collect ::<Vec <char >>() } ;($next :expr ,usize1 ) =>{read_value !($next ,usize ) -1 } ;($next :expr ,$t :ty ) =>{$next () .parse ::<$t >() .expect ("Parse error" ) } ;}

fn main() {
   input! {
      _n: usize,
      k: usize,
      _d: [usize; k],
   }
   let mut d = vec![true; 10];
   for i in _d {
      d[i] = false;
   }
   let mut n = _n;
   loop {
      let mut m = n;
      let mut ok = true;
      while m > 0 {
         if !d[m % 10] {
            ok = false;
            break;
         }
         m /= 10;
      }
      if ok {
         break;
      }
      n += 1;
   }
   println!("{}", n);
}


Measured memory_bytes: 4352
a = input()
X = int(a)

if 1800 <= X:
    print(1)
elif 1600 <= X:
    print(2)
elif 1400 <= X:
    print(3)
elif 1200 <= X:
    print(4)
elif 1000 <= X:
    print(5)
elif 800 <= X:
    print(6)
elif 600 <= X:
    print(7)
elif 400 <= X:
    print(8)

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

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	string s, ret;
	while(cin>>s) ret+=s[0];
	cout << ret << endl;
	return 0;
}


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

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

  long long A[K];
  for (long long i = 0; i < K; i++) {
    cin >> A[i];
  }

  if (A[K-1] > 2) {
    cout << "-1";
    return 0;
  }

  long long P[2] = {1, 2};
  for (long long i = K-2; i >= 0; i--) {
    if (A[i] >= A[i+1]*P[1]) {
      cout << "-1";
      return 0;
    } else {
      P[1] = (A[i+1]*P[1] - 1) / A[i] + 1;
      P[0] = (A[i+1]*P[0] - 1) / A[i] + 1;
    }
    if (P[0] == P[1]) {
      cout << "-1";
      return 0;
    }
  }
  cout << A[0]*P[0] << ' ' << A[0]*P[1] - 1;
  return 0;
}

Measured memory_bytes: 1024
s=input()
t=input()
if not len(s)>=1:
	print("No")
	exit()
if not len(s)<=10:
	print("No")
	exit()
if not len(t)==len(s)+1:
	print("No")
	exit()
if t[0:len(t)-1]==s:
    print("Yes")
else:
	print("No")


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

int main(){
    int n,x;    cin>>n>>x;
    int a[n];   for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    //for(int i=0;i<n;i++)cout<<a[i]<<endl;

    int ans=0;
    bool flag=true;
    for(int i=0;i<n;i++){
        if(a[i]<=x){
            x-=a[i];
            ans++;
        }else{
            flag=false;
            break;
        }
    }

    if(flag){
        while(x>=a[0]){
            x-=a[0];
            ans++;
        }
    }

    cout<<ans<<endl;




    return 0;
}


Measured memory_bytes: 256
/*---------------------------------

 @Author:   Dicer
 @DateTime: 2019-05-28 19:49:36

---------------------------------*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
inline ll qpow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res = (res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const int mod = 1e9+7;
const int MAXN = 2e5 + 7;

struct res{
	int id, sco;
	string city;
}s[233];
bool cmp(res a, res b){
	if(a.city == b.city)	return a.sco > b.sco;
	else	return a.city < b.city;
}
int main(int argc, char const *argv[])
{
	int n;
	cin >> n;
	for(int i = 1; i <= n; ++i){
		cin >> s[i].city >> s[i].sco;
		s[i].id = i;
	}
	sort(s+1, s+1+n, cmp);
	for(int i = 1; i <= n; ++i){
		cout << s[i].id << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int c, hc = 0;
	
	while(scanf("%d", &c)){
		int i, f = 0,  hc = 0, ka = 0;
		long long int ov[4000][2];
		if(c == 0) break;
		
		for(i = 0; c > i; i++){
			long long int a,b;
			int k, num, al = 0;
			
			scanf("%d%lld%lld",&num, &a, &b);
			for(k = 0; hc > k; k++){
				if(ov[k][0] == num){
					ov[k][1] += a*b;
					al = 1;
				}
			}
			if(al == 0){
				ov[hc][0] = num;
				ov[hc][1] = a*b;
				hc++;
			}
		}
		for(ka = 0; hc > ka; ka++){
			if(ov[ka][1] >= 1000000){
				printf("%lld\n", ov[ka][0]);
				f = 1;
			}
		}
		if(f == 0) printf("NA\n");
		f = 0;
		hc = 0;
	}
	
	return 0;
}

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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll calc(ll &m, ll p) {
    ll ret = 1;
    m += p;
    if (m >= 10) {
        ret++;
        m = (m / 10) + (m % 10);
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll M;
    cin >> M;
    ll ans = 0;
    vector<ll> v(M);
    REP(i, M) {
        ll d, c;
        cin >> d >> c;

        vector<ll> u;
        while (c > 1) {
            if (c % 2 == 1)
                u.push_back(d);
            c /= 2;
            ans += c;
            d = d + d;
            if (d >= 10) {
                d = (d / 10) + (d % 10);
                ans += c;
            }
        }
        u.push_back(d);
        ll n = u[0];
        REP(j, u.size() - 1) {
            ans += calc(n, u[j + 1]);
        }
        v[i] = n;
    }

    ll m = v[0];
    REP(i, M - 1) {
        ans += calc(m, v[i + 1]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
import collections
import sys

n = int(input())
d = list(map(int, input().split()))

cnt = collections.Counter(d)

if d[0]!=0:
    print(0)
    sys.exit(0)

if cnt[0]!=1:
    print(0)
    sys.exit(0)    
    
p = 1

for i in range(1,max(d)+1):
    p = (p * pow(cnt[i-1], cnt[i], 998244353))%998244353

print(p)

Measured memory_bytes: 19936
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var ND = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        var (N, D) = (ND[0], ND[1]);

        var ans = MathExt.DivideAndRoundUp(N, D * 2 + 1);

        WriteLine(ans);
    }
}

static class MathExt
{
    public static int DivideAndRoundUp(int x, int y) => (x + y - 1) / y; // (int)Math.Ceiling((double)x / (double)y);
    public static long DivideAndRoundUp(long x, long y) => (x + y - 1) / y;
}


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

int main() {
	int N, x, a;
	cin >> N >> x;
	vector<int> vec(N);
	int total = 0;
	int count = 0;
	for (int i = 0; i < N; i++) {
		cin >> a;
		vec.at(i) = a;
	}
	sort(vec.begin(), vec.end());
	for (int j = 0; j < N; j++) {
		total += vec.at(j);
		if (total <= x && j < N - 1) {
			count++;
		}
		else if (total < x && j == N - 1) {
			break;
		}
		else if (total == x && j == N - 1) {
			count++;
		}
		else {
			break;
		}
	}
	cout << count << endl;
}

Measured memory_bytes: 3636
#pragma GCC optimize("Ofast")
#include<stdio.h>
int main(void)
{
    int n = 0;
    char c=getchar_unlocked();
    while(c<='9'&&c>='0') {n = (n << 1) + (n << 3) + c - '0'; c=getchar_unlocked();}
    n %= 1000;
    if(n) {
        printf("%d", 1000 - n);
        return 0;
    }
    puts("0");
    return 0;
}


Measured memory_bytes: 1604
n,*a=$<.read.split.map(&:to_i)
t=a.each_with_index.sort_by{|e,i|i-e*100000}.chunk(&:first).map{|c,r|[c,r[0][1],r.size]}
buf=[0]*n
cur,acc=1.0/0,0
(t.size-1).times{|i|
  r,nt,sz=*t[i]
  cur=[cur,nt].min
  acc+=sz
  buf[cur]+=acc*(r-t[i+1][0])
}
buf[0]+=t[-1][0]*n
puts buf


Measured memory_bytes: 20060
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def main():
    N, K = map(int, input().split())
    snuke = [0]*N
    for k in range(K):
        d = int(input())
        A = list(map(int, input().split()))
        for a in A:
            snuke[a-1] += 1

    cnt = 0
    for s in snuke:
        if s == 0:
            cnt += 1
    print(cnt)

    return


if __name__ == '__main__':
    main()


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

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

const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
  int N;
  cin >> N;
  ll a[N];
  for (int i = 0; i < N; i++) cin >> a[i];

  int cnt = 0;
  for (int i = 0; i < N; i++) {
    if (a[i] < 0) {
      cnt++;
      a[i] *= -1;
    }
  }

  sort(a, a + N);
  ll ans = 0;
  if (cnt & 1) {
    for (int i = 1; i < N; i++) ans += a[i];
    cout << ans - a[0] << endl;
  } else {
    for (int i = 0; i < N; i++) ans += a[i];
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define ll long long
#define coYes cout << "Yes" << endl;
#define coYES cout << "YES" << endl;
#define coyes cout << "yes" << endl;
#define coNo cout << "No" << endl;
#define coNO cout << "NO" << endl;
#define cono cout << "no" << endl;
#define BIT_FLAG_0 (1<<0) // 0000 0000 0000 0001
int gcd(int a, int b){
    if(a%b == 0){
        return b;
    }else{
    return gcd(b, a%b);
    }
}

int main(){
    int a,b,n=1,ans=0;
    cin >> a >> b;
    while(n<b){
        n+=a-1;
        ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3580
#include<stdio.h>
#include<iostream>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<algorithm>
#include<string.h>
#include<functional>
#include<limits.h>
#include<stdlib.h>
#include<string>
#include<unordered_map>
#include <iomanip>
using namespace std;
 
#define intmax INT_MAX
#define lmax LONG_MAX
#define uintmax UINT_MAX
#define ulmax ULONG_MAX
#define llmax LLONG_MAX
#define ll long long
#define rep(i,a,N) for((i)=(a);(i)<(N);(i)++)
#define rrp(i,N,a) for((i)=(N)-1;(i)>=(a);(i)--)
#define llfor ll i,j,k
#define sc(a) cin>>a
#define pr(a) cout<<a<<endl
#define pY puts("YES")
#define pN puts("NO")
#define py puts("Yes")
#define pn puts("No")
#define pnn printf("\n")
#define sort(a) sort(a.begin(),a.end())
#define push(a,b) (a).push_back(b)
#define llvec vector<vector<ll>>
#define charvec vector<vector<char>>
#define sizeoof(a,b) (a,vector<ll>(b))
#define llpvec vector<pair<ll,ll>>
/*繰り上げ除算*/ll cei(ll x,ll y){ll ans=x/y;if(x%y!=0)ans++;return ans;}
/*最大公約数*/ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*最小公倍数*/ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
/*n乗*/ll llpow(ll x,ll n){ll i,ans=1;rep(i,0,n)ans*=x;return ans;}
/*階乗*/ll fact(ll x){ll i,ans=1;rep(i,0,x)ans*=(x-i);return ans;}
/*nCr*/ll ncr(ll n,ll r){return fact(n)/fact(r)/fact(n-r);}
/*nPr*/ll npr(ll n,ll r){return fact(n)/fact(n-r);}
/*primejudge*/bool prime(ll a){if(a<=1)return false;ll i;for(i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
ll ans=0;llfor;///////////////////////////////////////////////////////////
int main(){
  string a,b;
  cin>>a>>b;
  string S="D";
  if(a==b) S="H";
  cout<<S;
return 0;}

Measured memory_bytes: 3548
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
int main(void){
  int n;
  cin>>n;
  vector<string> s(n);
  vector<map<char,int>> hoge(n);
  for(int i=0; i<n; i++){
    cin>>s.at(i);
    sort(s.at(i).begin(),s.at(i).end());
  }
  string ans="";
  char now='a';
  while(now<='z'){
    bool ok=true;
    for(int i=0; i<n; i++){
      if(s.at(i)[0]!=now){
        ok=false;
      }
    }
    if(ok){
      for(int i=0; i<n; i++){
        s.at(i).erase(s.at(i).begin());
      }
      ans+=now;
    }else{
      for(int i=0; i<n; i++){
        for(int j=0; j<s.at(i).size(); j+=0){
          if(s.at(i)[0]==now){
            s.at(i).erase(s.at(i).begin());
          }else{
            break;
          }
        }
      }
      now+=1;
    }
  }
  cout<<ans<<endl;
}

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

using namespace std;

#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.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 (a>b) { a = b; return 1; } return 0; }
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = 1e18;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair

vector<vector<vector<double> > > dp(301, vector<vector<double> >(301, vector<double>(301, -1)));
int n;

double dfs(int i, int j, int k) {
  if (dp[i][j][k] >= 0) {
    return dp[i][j][k];
  }
  dp[i][j][k] = (double)n / (i + j + k);
  if (i != 0) {
    dp[i][j][k] += dfs(i - 1, j + 1, k) * i / (double)(i + j + k);
  }
  if (j != 0) {
    dp[i][j][k] += dfs(i, j - 1, k + 1) * j / (double)(i + j + k);
  }
  if (k != 0) {
    dp[i][j][k] += dfs(i, j, k - 1) * k / (double)(i + j + k);
  }
  return dp[i][j][k];
}
                                           

int main() {
  cin >> n;
  int i0 = 0, j0 = 0, k0 = 0;
  rep (i, n) {
    int a;
    cin >> a;
    if (a == 1) {
      k0++;
    }
    else if (a == 2) {
      j0++;
    }
    else {
      i0++;
    }
  }
  dp[0][0][0] = 0;
  Sp(dfs(i0, j0, k0));
}


Measured memory_bytes: 217088
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
#include<set>
#define rep(i,N) for(int i=0;i<N;i++)

long long  INF=1000000000000000000;
long long mod=1000000007;
using namespace std;

int main(){

string s;
cin>>s;
int k;
cin>>k;
vector<vector<int>>v(26);//各alphabetの文字の格納位置

rep(i,s.size()){
    v[s[i]-'a'].push_back(i);
}
set<string>ans;
int cnt=0;
rep(i,26){
    int t=0;
    if(v[i].empty())continue;
    while(t<v[i].size()){
        int start=v[i][t];
        string p;
            while(start<s.size() && p.size()<=k){
            p.append(1,s[start]);
            if(ans.find(p)==ans.end()){
            ans.insert(p);
            cnt++;
            }
            start++;
        }
        t++;
    }
    if(cnt>=k)break;
}

auto it=ans.begin();

it=next(it,k-1);

cout<<*it<<endl;

 return 0;
}
/*
aba
4

b

atcoderandatcodeer
5

andat

z
1

z
*/

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
using namespace std;
using P = pair<int, int>;
int mod = (int) 1e9 + 7;

int is_prime(long n){
    
    if(n == 1) return 0;
    if(n == 2) return 1;
    long i = 2;
    while(i * i <= n){
        if(n % i == 0) return 0;
        i++;
    }
    return 1;

}

int main(){
    
    long n;
    cin >> n;
    
    long i = 2;
    int ans = 0;
    
    if (n == 1){
        cout << ans << "\n";
        return 0;
    }
    
    while(1){
        if(n == 1) break;
        
        if(is_prime(n) == 1){
            ans++;
            break;
        }
        
        while(n % i > 0) i++;
        
        int count = 0;
        while(n % i == 0){
            count++;
            n /= i;
        }
        
        int x = 0;
        while(count - x > 0){
            x++;
            count -= x;
        }
        
        ans += x;
        
        i++;
    }
    
    cout << ans << "\n";
    
    return 0;
}



Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
using Long = long long;

template <typename W>
using Edge = pair<int, W>;

template <typename W>
using WeightedGraph = vector<vector<Edge<W>>>;

// 時間計算量 ; O(VE)
template <typename W>
tuple<vector<W>, bool> bellman_ford(int s, int V_size, WeightedGraph<W> &G)
{
    // true -> 負の閉路なし, false -> 負の閉路あり
    // s : 始点, G : 隣接リスト G[v1][v2] : (頂点, 重み)
    const W INF = numeric_limits<W>::max();
    // 初期化
    vector<W> d(V_size, INF);
    d[s] = 0;
    bool update = true;

    for (int k = 0; update && k < V_size; k++)
    {
        update = false;
        for (int i = 0; i < (int)G.size(); i++)
        {
            for (auto &&p : G[i])
            {
                if (d[i] != INF && d[p.first] > d[i] + p.second)
                {
                    d[p.first] = d[i] + p.second;
                    update = true;
                    if (k == (V_size - 1))
                        return forward_as_tuple(d, false);
                }
            }
        }
    }
    return forward_as_tuple(d, true);
}

int main(void)
{
    int V, E, r;
    int s, t, d;
    cin >> V >> E >> r;
    WeightedGraph<int> G(V);
    for (int i = 0; i < E; i++)
    {
        cin >> s >> t >> d;
        G[s].emplace_back(t, d);
    }

    vector<int> D;
    bool flg;
    tie(D, flg) = bellman_ford(r, V, G);
    if (!flg)
    {
        cout << "NEGATIVE CYCLE" << endl;
        return 0;
    }
    for (int i = 0; i < V; i++)
    {
        if (D[i] == numeric_limits<int>::max())
        {
            cout << "INF" << endl;
        }
        else
        {
            cout << D[i] << endl;
        }
    }
}


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define gcd(a,b) __gcd(a,b)
#define mem(z,i) memset(z,i,sizeof(z))
const int mod=(int)1e9+7;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int n,s=0;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        s+=b-a+1;
    }
    cout<<s;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[200010];
int main(){
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int j=1,f=0;
    for(int i=0;i<n;i++){
        if(a[i]==j){
            j++;
            f=1;
        }
    }
    if(f==0)
        cout<<"-1";
    else
        cout<<n-j+1;



}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF = 1e9+7;


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

	int n;
	cin >> n;
	vector<int> h(n);
	rep(i, n) cin >> h.at(i);
	int ans = 0;
	int now = h.at(0);
	rep(i, n){
		if(h.at(i) >= now){
			ans++;
			now = h.at(i);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
MOD = 10**9+7

H,W = imn()
a = [input() for _ in range(H)]
dp = [[0 for _ in range(W+1)] for _ in range(H+1)]
dp[0][0] = 1


for i in range(H):
    for j in range(W):
        if i + 1 < H and a[i+1][j] == '.': dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
        if j + 1 < W and a[i][j+1] == '.': dp[i][j+1] = (dp[i][j+1] + dp[i][j]) % MOD
print(dp[H-1][W-1])

Measured memory_bytes: 81240
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

using LL = long long;
const int MAXN = 1e6 + 5;
int N, M, Q;
int p[MAXN];
struct node {
  int l, r;
  int id;
} q[MAXN];
bool cmp(node a, node b);
int mark[MAXN];
int bit[MAXN];
void update(int pos, int key);
int query(int pos);
int ans[MAXN];

int main() {
  scanf("%d%d", &N, &Q);
  for (int i = 1; i <= N; i++) scanf("%d", p + i);
  for (int i = 1; i <= Q; i++) {
    scanf("%d%d", &q[i].l, &q[i].r);
    q[i].id = i;
  }
  sort(q + 1, q + 1 + Q, cmp);
  for (int i = 1, j = 1; i <= Q; i++) {
    // cout << q[i].l << " " << q[i].r << endl;
    while (j <= q[i].r) {
      if (mark[p[j]]) update(mark[p[j]], -1);
      mark[p[j]] = j;
      update(mark[p[j]], 1);
      j++;
    }
    ans[q[i].id] = query(q[i].r) - query(q[i].l - 1);
  }
  for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]);
  return 0;
}

#define lowbit(x) (x & (-x))
int query(int pos) {
  int res = 0;
  while (pos) {
    res += bit[pos];
    pos -= lowbit(pos);
  }
  return res;
}

void update(int pos, int key) {
  while (pos <= N) {
    bit[pos] += key;
    pos += lowbit(pos);
  }
}

bool cmp(node a, node b) {
  if (a.r == b.r) return a.l < b.l;
  return a.r < b.r;
}

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

int main(){
    int N;
    cin >> N;
    int a,b,c,d;
    a=N/1000;
    b=(N-1000*a)/100;
    c=(N-1000*a-100*b)/10;
    d=N-1000*a-100*b-10*c;

    if( (a==b && b==c) || (b==c && c==d) ) {cout << "Yes" << endl;}
    else {cout << "No" << endl;}
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> vet;
int main(){
	int n;
	cin >>n;
	vet.resize(n);
	
	for(int i =0;i<n;i++) cin >> vet[i];
	sort(vet.begin(),vet.end());
	cout<<(vet.back()-vet[0]);
}

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

#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
const int INF = 100000;

int get_times(int x){
    int times = 0;
    while(x > 0 && x % 2 == 0){
        times++;
        x /= 2;
    }
    return times;
}

// x = i/W, y = i%W;
// xy = j * W + i;
int main() {
    int N;
    cin >> N;
    vector<int> A(N), B(N - 1);
    string S;
    cin >> S;
    int only02flag = 1;
    rep(i, N){
        B[i] = S[i] - '1';
        if (B[i] == 1){
           only02flag = 0;
        }
    }

    rep(i, N){
        if (B[i] == 2){
            if (only02flag){
                B[i] = 1;
            } else {
                B[i] = 0;
            }
        }
    }
    
    int ans = 0;
    int times = 0;
    int nCk = 1;
    rep(i, N){
        if (i >= 1){
            times += get_times(N -i);
            times -= get_times(i);
            nCk *= (N - i);
            nCk /= i;
        }
        if (times == 0){
            ans ^= B[i];
        }
        //cout << i << " " << N + 1 - i << " " << nCk << " " << times << endl;
    }
    if (only02flag){
        cout << ans * 2;
    } else {
        cout << ans;
    }

    return 0;
}


Measured memory_bytes: 9220
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

ll p[55]={1ll},s[55]={1ll};

int main(void){
	int n,i;
	ll x,ans=0ll,t;
	cin >> n >> x;
	for(i=0; i<n; ++i){
		p[i+1] = 2*p[i]+1;
		s[i+1] = 2*s[i]+3;
	}
	while(n){
		t = (1+s[n])/2;
		if(x==1ll){
			break;
		}else if(x==s[n]){
			ans += p[n];
			break;
		}else if(x<t){
			--x;
		}else{
			ans += p[n-1];
			ans += 1;
			x -= t;
			if(!x){
				break;
			}
		}
		--n;
	}
	if(n==0ll && x==1ll){
		++ans;
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
ll pow3, cnt;
ll inv3;
int A[MAX_N], C[MAX_N];
int CF[MAX_N], CB[MAX_N];
string str;

ll mod_pow(ll a, ll n) {
	if(n == 0) return 1;
	ll res = mod_pow(a, n / 2);
	if(n % 2 == 0) return res * res % mod;
	else return res * res % mod * a % mod;
}

void solve() {
	cin >> str; N = sz(str);
	pow3 = 1; cnt = 0;
	rep(i, 0, N) {
		if(str[i] == '?') {
			MUL(pow3, 3);
			cnt++;
		}
	}
	inv3 = mod_pow(3, mod - 2);
	rep(i, 0, N) {
		A[i + 1] = A[i] + (str[i] == 'A');
		CF[i + 1] = CF[i] + (str[i] == '?');
	}
	rer(i, N, 0) {
		C[i] = C[i + 1] + (str[i] == 'C');
		CB[i] = CB[i + 1] + (str[i] == '?');
	}
	ll res = 0;
	rep(i, 1, N - 1) {
		if(str[i] == 'B') {
			ADD(res, ((A[i] + CF[i] * inv3) % mod) * ((C[i + 1] + CB[i + 1] * inv3) % mod) % mod);
		}
		else if(str[i] == '?'){
			ADD(res, ((A[i] + CF[i] * inv3) % mod) * ((C[i + 1] + CB[i + 1] * inv3) % mod) % mod * inv3 % mod);
		}
	}
	cout << res * pow3 % mod << "\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



Measured memory_bytes: 2000
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main(){

    input!{
        a: usize,
        b: usize,
    }
    println!("{}", std::cmp::max(2*a-1, std::cmp::max(2*b-1, a+b)));

}

Measured memory_bytes: 4352
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    n, k = map(int, readline().split())

    COM_MAX = n

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1

    for i in range(2, COM_MAX + 1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    def com(n, r):
        if n < 0 or r < 0 or n < r:
            return 0
        return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD

    ans = 0
    for r in range(min(n, k + 1)):
        ans = (ans + com(n, r) * com(n - 1, r)) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 71964
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[]args) {
		try(Scanner scan = new Scanner(System.in)){
			int N = scan.nextInt();
			int[] v = new int[N];
			
			for(int i =0;i<N;i++) {
				v[i] = scan.nextInt();
			}
			
			Arrays.sort(v);
			
			double saigo=v[0];
			
			for(int i = 1;i<=N-1;i++) {
				saigo =(saigo+v[i])/2; 
			}
			
			
			System.out.println(saigo);
			
			
			
			
			
			
			
			
		}
		
		
	}
		

}


Measured memory_bytes: 21204
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
using ll = long long;
int INF = 1000000009;
int main()
{
    int n,a,b;
    cin >> n >> a >> b;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int x = i;
        int sum = 0;
        while (x)
        {
            sum += (x % 10);
            x /= 10;
        }
        if(a <= sum && sum <= b){
            ans += i;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <sstream>
#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++)
#define INF 1e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
#define downque(que)  priority_queue<ll> que;
#define upque(que) priority_queue<ll, vector<int>, greater<int>> que;

int flag(int mask,int i){
   if(mask&(1<<i))return true;
   else return false;
}

int main(){
   string s; cin>>s;
   int v[4];
   REP(i,4)v[i]=stoll(s.substr(i,1));

 //ビット全探索
  for(int mask=0;mask<(1<<3);mask++){ //1000
   
      int sum=v[0];
      string t="";
      t+=s[0];

      for(int i=0;i<3;i++){
            if(flag(mask,i)){
               sum+=v[i+1];
               t+='+';
         }else{
          sum-=v[i+1];
          t+='-';
         }
          t+=s[i+1];
      }
     if(sum==7){
       t+="=7";
       cout<<t<<endl;
       break;
     }
  }
} 
 

Measured memory_bytes: 256
import sys
import os
import math

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

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

MOD = 10 ** 9 + 7


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

    N = ii()
    ret = set()
    for n in range(N):
        i = [ii()]
        ret ^= set(i)
    print(len(ret))


if __name__ == '__main__':
    main()


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

typedef long long ll;

#define rep(i, n) for(ll i = 0; i < (int)(n); i++)
const ll INF = 1e18;
const ll mod = 1e9+7;

int main() {
    ll h,w,K;
    cin>>h>>w>>K;
    vector<string> s(h);
    rep(i,h)cin>>s[i];
    ll ans=INF;
    rep(i,1<<(h-1)){
      vector<ll>S;
      //S[0]=INF;
      ll C=0;
      ll Cf=0;
      rep(j,h-1){
        if (i & (1<<j)){

          S.push_back(j);
          //cout<<i<<'i'<<endl;
      //    C++;
        }
        }
        Cf=S.size();

        S.push_back(h-1);
          C=S.size();
//cout<<C<<'c'<<endl;
        //和を入れる
        ll maxsm=0;
        vector<vector<int>> sm(C+2,vector<int> (w));
        rep(j,w){
        //  cout<<j<<'w'<<endl;
            ll cnt=0;
            ll now=0;
          //  if (C==0) now=0;
          rep(k,h){
          //  cout<<k<<'k'<<endl;
            if (s[k][j]=='1'){

              cnt++;
              maxsm=max(maxsm,cnt);
            }
              if (k==S[now]){

    //cout<<j<<'w'<<now<<'n'<<k<<'k'<<endl;

                sm[now][j]=cnt;
              //  cout<<cnt<<'C'<<endl;
                cnt=0;
                now++;

            }
          }
        }

         if (i==0) {

           rep(j,C){
            // cout<<j<<endl;
        //   rep(k,w)cout<<sm[j][k];
         }
        // cout<<endl;
         }
        if (maxsm>K) continue;
        //たての分け方の評価
        ll Cnt=0;
        vector<ll> v(C);
        vector<ll> temp(C);
        rep(j,w){

          ll cn=0;
          rep(k,C){
            temp[k]+=sm[k][j];
            cn=max(cn,temp[k]);
          //  cout<<temp[k]<<'j'<<j<<'k'<<k<<endl;
          }
          if (cn>K){
            Cnt++;
          //  cout<<cn<<' '<<Cnt<<endl;
            rep(k,C){
              temp[k]=sm[k][j];
            }
          }
        }

        ans=min(ans,Cnt+Cf);
      }


cout<<ans;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

typedef long long ll;

const ll INF = 1000000000000000000;

ll mini(ll a, ll b)
{
    if (a < b)
        return a;
    return b;
}

ll bez(ll a)
{
    if (a >= 0)
        return a;
    return -a;
}

int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    vector<ll> a(n);
    ll s = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        s += a[i];
    }
    ll odp = INF;
    ll p = 0, d = 0;
    for (int i = 0; i < n - 1; ++i)
    {
        p += a[i];
        d = s - p;
        odp = mini(odp, bez(p - d));
    }
    cout << odp;
    return 0;
}


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

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
// #define MOD 998244353 
#define MEM_SIZE 1000100
#define DEBUG_OUT true
#define ALL(x) (x).begin(), (x).end()


template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; abort();}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }


int mat_sum(vector<vector<int > > & mat,int x1,int y1,int x2,int y2)
{
  return mat[y2][x2] - mat[y2][x1] - mat[y1][x2] + mat[y1][x1];
}
void solve(void)
{
  //https://atcoder.jp/contests/abc086/submissions/2001424
  vector<vector<int> >  bb (4010,vector<int>(4010,0));
  vector<vector<int> >  ww (4010,vector<int>(4010,0));
  vector<vector<int> >  bbcc (4010,vector<int>(4010,0));
  vector<vector<int> >  wwcc (4010,vector<int>(4010,0));
  int n,k;cin>>n>>k;
  int k2 =k*2;
  for (int i = 0; i < n; i++)
  {
    int x,y;char c;
    cin>>x>>y>>c;
    x %= k2;
    y %= k2;
    if(c =='B')
    {
      bb[y][x]++;
      bb[y+k2][x]++;
      bb[y][x+k2]++;
      bb[y+k2][x+k2]++;
    }
    else
    {
      ww[y][x]++;
      ww[y+k2][x]++;
      ww[y][x+k2]++;
      ww[y+k2][x+k2]++;
    }
  }
  for (int y = 0; y < k2*2; y++)
  {
    for (int x = 0; x < k2*2; x++)
    {
      bbcc[y+1][x+1] += bb[y][x] + bbcc[y+1][x] + bbcc[y][x+1] - bbcc[y][x];
      wwcc[y+1][x+1] += ww[y][x] + wwcc[y+1][x] + wwcc[y][x+1] - wwcc[y][x];
    }
    
  }
  int res = 0;
  for (int x1  = 0; x1  < k2; x1 ++)
  {
    for (int y1 = 0; y1 < k2; y1++)
    {
      int x2 = x1 + k;
      int y2 = y1 + k;
      int sum = mat_sum(bbcc,x1,y1,x2,y2) +  mat_sum(bbcc,x1+k,y1+k,x2+k,y2+k); 
      sum += mat_sum(wwcc,x2,y1,x2+k,y2) +  mat_sum(wwcc,x1,y2,x2,y2+k);    
       chmax(res,sum);
    
    }

  }
  cout<<res<<endl;
  
  

  return;
}

int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(11);
  solve();

  return 0;
}


Measured memory_bytes: 254996
import collections
S, T = input(), input()

S_char_count = [[c, n] for c, n in collections.Counter(S).items()]
T_char_count = [[c, n] for c, n in collections.Counter(T).items()]
S_char_count.sort(key=lambda S_char_count: S_char_count[1])
T_char_count.sort(key=lambda T_char_count: T_char_count[1])

ans = 'Yes'
if len(S_char_count) == len(T_char_count):
  for i in range(len(S_char_count)):
    if S_char_count[i][1] != T_char_count[i][1]:
      ans = 'No'
      break
else:
  ans = 'No'

print(ans)


Measured memory_bytes: 4136
import sys

c = [list(map(int, input().split())) for _ in range(3)]

b = [c[0][0], c[0][1], c[0][2]]
a = [0, c[1][0] - b[0], c[2][0] - b[0]]

for i in range(3):
    for j in range(3):
        if c[i][j] != a[i] + b[j]:
            print('No')
            sys.exit()
print('Yes')


Measured memory_bytes: 3064
import java.util.Scanner;

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

    long M = 1_000_000_007;
    int N = scanner.nextInt();
    char[] s = scanner.next().toCharArray();

    long[][] dp = new long[N][N];
    dp[0][0] = 1;
    for (int i = 1; i < N; i++) {
      if (s[i - 1] == '<') for (int j = 1; j <= i; j++) dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - 1]) % M;
      else for (int j = i - 1; j >= 0; j--) dp[i][j] = (dp[i][j + 1] + dp[i - 1][j]) % M;
    }
    long res = 0;
    for (int i = 0; i < N; i++) {
      res += dp[N - 1][i];
      if (res > M) res -= M;
    }
    System.out.println(res);
  }
}


Measured memory_bytes: 130892
#include<bits/stdc++.h>
#define ll long long
#define rep(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
int main()
{
  int l,n,m,ans,a[10];
  cin>>n;
  a[0]=n%10;
  a[1]=n/10%10;
  a[2]=n/10/10%10;
  a[3]=n/10/10/10%10;
  a[4]=n/10/10/10/10%10;
  a[5]=n/10/10/10/10/10%10;
  rep(i,6){if(a[i]!=0)m++;
          }
  rep(i,6){if(a[i]==1)l++;
          }
  if(m==1&&l==1)ans=(a[0]+a[1]+a[2]+a[3]+a[4]+a[5])*10;
  else ans=a[0]+a[1]+a[2]+a[3]+a[4]+a[5];
  printf("%d",ans);
  
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const long long mod=1e9+7;
const int N=1e5+10;
char ch[N];
int n;
long long s[N][2],f[N][2],sum[N],mi[N],tot,ans;
int main()
{
	scanf("%s",ch+1);
	n=strlen(ch+1);
	tot=1;
	sum[0]=0;
	mi[0]=1;
	for (int i=1;i<=n;i++) 
	{
		sum[i]=(tot*i)%mod;
		tot=tot*3%mod;
		mi[i]=mi[i-1]*3%mod;
	}
	for (int i=1;i<=n;i++)
	{
		s[i][1]=s[i-1][1]+(ch[i]=='?');
		s[i][0]=s[i-1][0]+(ch[i]=='A');
	}
	for (int i=n;i>=1;i--)
	{
		f[i][1]=f[i+1][1]+(ch[i]=='?');
		f[i][0]=f[i+1][0]+(ch[i]=='C');
	}
	for (int i=2;i<=n;i++)
	{
		if (ch[i]=='?'||ch[i]=='B')
		{
			ans+=(s[i][0]*mi[s[i-1][1]]%mod+sum[s[i-1][1]])%mod*((f[i+1][0]*mi[f[i+1][1]])%mod+sum[f[i+1][1]])%mod;
			ans%=mod;
		}
	}
	
	cout<<ans;
	return 0;
} 




Measured memory_bytes: 4992
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

const int LIM=1000000;

int sosu[LIM];

int main() {
	sosu[0]=sosu[1]=1;
	for(int i=0;i<LIM;i++){
		if(sosu[i])continue;
		for(int j=i*2;j<LIM;j+=i){
			sosu[j]=1;
		}
	}
	Int sos[LIM]={0};
	int i,n=1;
	Int num=0;
	for(i=0;i<LIM;i++){
		if(!sosu[i])sos[n++]=(num+=i);
	}
	while(n=in()){
		cout<<sos[n]<<endl;
	}
}

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


int main(){
  int A,B;
  cin >> A >> B;
  if (A==1 && B== 1){
    cout << 1000000 << endl;
    return 0;
  }else{
    int a,b;
    if (A<=4){
      a = 100000*(4-A);
    }else{
      a = 0;
    }
    if (B<=4){
      b = 100000*(4-B);
    }else{
      b=0;
    }
    cout << a+b << endl;
  }
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.Set;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AKIBA solver = new AKIBA();
        solver.solve(1, in, out);
        out.close();
    }

    static class AKIBA {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            String dest = "AKIHABARA";
            String input = in.next();

            Set<String> possibleSources = new TreeSet<>();
            generate(dest, 0, "", possibleSources);

            out.println(possibleSources.contains(input) ? "YES" : "NO");
        }

        private void generate(String dest, int idx, String current, Set<String> possibleSources) {
            if (idx == dest.length()) {
                possibleSources.add(current);
            } else {
                if (dest.charAt(idx) == 'A') {
                    generate(dest, idx + 1, current, possibleSources);
                }
                generate(dest, idx + 1, current + dest.charAt(idx), possibleSources);
            }
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

    }
}



Measured memory_bytes: 21588
#include <iostream>

using namespace std;

int main(){
	int n; int i; int money = 100000;
	cin >> n;
	for (i = 1; i <= n; i++){
		money = money * 1.05;
		int hasuu = money % 1000;
		if (hasuu > 0){
			money = money - hasuu + 1000;
		}
	}
	cout << money << endl;

	return  0;
}

Measured memory_bytes: 1160
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		
		int S = scan.nextInt();
		
		System.out.println(S / 3600 + ":" + S % 3600 / 60 + ":" + S % 3600 % 60);
	}

}


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

int main()
{
    uint64_t A, B;
    cin >> A >> B;

    uint64_t ans;

    // F(A, B) = F(0, A-1) + F(0, B)

    if ((A - 1) % 2 == 0)
    {
        // A - 1 is even
        if (((A - 1) / 2) % 2 == 0)
        {
            // (A - 1) / 2 is even
            ans = 0 ^ (A - 1);
        }
        else
        {
            // (A - 1) / 2 is odd
            ans = 1 ^ (A - 1);
        }
    }
    else {
        // A - 1 is odd
        if (((A - 1) / 2) % 2 == 0) {
            // (A - 1) / 2 is even
            ans = 0 ^ (A - 2) ^ (A - 1);
        }
        else {
            // (A - 1) / 2 is odd
            ans = 1 ^ (A - 2) ^ (A - 1);
        }
    }

    if (B % 2 == 0) {
        // B is even
        if ((B / 2) % 2 == 0)
        {
            // B / 2 is even
            ans = ans ^ 0 ^ B;
        }
        else
        {
            // B / 2 is odd
            ans = ans ^ 1 ^ B;
        }
    }
    else {
        // B is odd
        if ((B / 2) % 2 == 0) {
            // B / 2 is even
            ans = ans ^ 0 ^ (B - 1) ^ B;
        }
        else {
            // B / 2 is odd
            ans = ans ^ 1 ^ (B - 1) ^ B;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384