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

typedef long long ll;
const ll MOD = 1e9+7;
const ll INF = 1e18+10;

int n;
ll a[405],s[405],dp[405][405];

ll solve(int from,int to){
    if(from>=to)dp[from][to]=0;
    if(from+1==to)dp[from][to]=a[from]+a[to];
    if(dp[from][to]!=INF)return dp[from][to];

    for(int k=from;k<=to;k++){
        dp[from][to]=min(dp[from][to],solve(from,k)+solve(k+1,to)+s[to]-s[from-1]);
    }
    return dp[from][to];
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];

    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=INF;

    cout<<solve(1,n);

    return 0;
}


Measured memory_bytes: 1536
/* ****mittal**** */
#include<bits/stdc++.h>
#define ll          long long int 
#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 jell        998244353
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define repr(i,a,b)   for(ll int i=a;i>=b;i--)
#define lbnd    lower_bound
#define ubnd        upper_bound
#define mp          make_pair
#define DEC(N)  cout << std::fixed; cout << setprecision(N);
using namespace std;
ll add(ll x,ll y)
{
return (x%hell+y%hell)%hell;
}
ll mul(ll x,ll y)
{
return ((x%hell)*(y%hell))%hell;
}
ll sub(ll x,ll y)
{
return (x-y+hell)%hell;
}
#define N  100005
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
   //cin>>t;
    for(int ok=1;ok<=t;ok++)
    {
        
     ll n,m,k;
     cin>>n>>m>>k;
     std::vector<ll> a,b;
     ll x=0;
     for(int i=1;i<=n;i++)
     {
         ll p;
         cin>>p;
         x+=p;
         a.pb(x);
     }
     x=0;
     for(int i=1;i<=m;i++)
     {
          ll p;
         cin>>p;
         x+=p;
         b.pb(x);
     }
     ll ans=0;
     for(ll i=0;i<=n;i++)
     {
      ll o;
        if(i==0)
        {
             o=k;
        }
        else
        {
           o=k-a[i-1];
        }
       // cout<<o<<endl;
        if(o<0)
          break;
        else
        {
            auto op=upper_bound(all(b),o)-b.begin();
            ans=max(ans,i+op);
        }
     }
     cout<<ans;
    }
    return 0;
}

Measured memory_bytes: 7956
import java.util.*;
public class Main
{
  public static void main(String[] args )
  {
    Scanner scn = new Scanner(System.in) ;
    
    int n = scn.nextInt() ;
    
    int[] arr =new int[n] ;
    
    for(int i =0 ; i < n; i++ ) arr[i] = scn.nextInt() ;
    
    
    if( n== 1 )
    {
     System.out.print(0) ; 
    }
    else{
    long[] dp = new long[n];
    
      dp[0] =  0 ; 
      dp[1] =  (long)Math.abs(arr[1] - arr[0] ) ;
      
      for(int i =2 ; i < n; i++ )
      {
        
         long opt1  =  dp[i-1] + (long)Math.abs(arr[i] - arr[i-1] ) ;
        
         long opt2  =  dp[i-2] + (long)Math.abs(arr[i] - arr[i-2] ) ;
       
        dp[i] =  Math.min(opt1 , opt2 ) ; 
        
        
     }
      
      System.out.print(dp[n-1]) ;
    
    }
    
    
    
  }
  
  
}


Measured memory_bytes: 59412
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;

void solve(long long N, long long K, string S){
	ll c = 0;
	rep(i, N-1) {
		if (S[i] != S[i+1]) ++c;
	}
	cout << N-1-max(c-2*K,0LL) << endl;
}

int main(){	
	string S;
	long long N;
	long long K;
	scanf("%lld",&N);
	scanf("%lld",&K);
	cin >> S;
	solve(N, K, S);
	return 0;
}



Measured memory_bytes: 512
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner a = new Scanner(System.in);
		int R = a.nextInt();
		if(R < 1200) {
			System.out.println("ABC");
		}else if(R < 2800) {
			System.out.println("ARC");
		}else {
			System.out.println("AGC");
		}
   }
}

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

int dp[100];

//最大公約数
int gcd(int x, int y){
  if(x % y == 0) return 1;
  return gcd(y, x % y);
}
//最小公倍数
int lcm(int x, int y){
  return x * y / gcd(x, y);
}
//フィボナッチ数列
//配列dpを-1で初期化する
int fib(int n){
  if(n == 0 || n == 1) return dp[n] = 1;
  if(dp[n] != -1) return dp[n];
  return dp[n] = fib(n - 1) + fib(n - 2);
}
//階乗計算(factorial)
int fact(int n){
  if(n = 1) return 1;
  return n * fact(n - 1);
}
//累乗計算(Exponentiation)
//x**y
ll expo(int x, int y){
  ll ans = 1;
  rep(i, y){
    ans *= x;
  }
  return ans;
}
//桁数
int keta(ll x){
  if(x == 0) return 1;
  int res = 0;
  while(x){
    x /= 10;
    res++;
  }
  return res;
}


int main(){
  int n, h[100010];
  cin >> n;
  rep(i, n) cin >> h[i];

  int ans = 0;
  int count = 0;
  REP(i, n){
    if(h[i] <= h[i-1]) {
      count ++;
      if(count >= ans) ans = count;
    }
    else{
      if(count >= ans) ans = count;
      count = 0;
    }
  }
  cout << ans << endl;
}


/*





















*/


Measured memory_bytes: 640
// --------------------<optimizations>--------------------
#pragma GCC optimize("O3")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)\
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)\
#pragma GCC optimize("unroll-loops")

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define F first
#define S second
#define ld long double
#define built __builtin_popcountll
#define mst(a,i) memset(a,i,sizeof(a))
#define all(x) x.begin(),x.end()
#define itit(it,a) for(auto it=(a).begin(); it!=(a).end(); it++)
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define repr(i,a,b) for(ll i=a; i>b; i--)
#define reprr(i,a,b) for(ll i=a; i>=b; i--)
#define pi 3.14159265358979323846264338327950288419716939937510582097494459230
ll max3(ll x,ll y,ll z) {return max(max(x,y),z);}
ll min3(ll x,ll y,ll z) {return min(min(x,y),z);}
const ll N=1e5+10,M=2e5+10,M2=1e6+10,mod=1e9+7,inf=1e17+10;
const int INF=1e9+7;
void add(int& a, int b) {a+=b;if(a>=mod){a-=mod;}}

#define trace(...) cerr<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
    cerr<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
    const char *comma=strchr(names+1,',');
    cerr.write(names,comma-names)<<" : "<<arg1<<" | ";
    __f(comma+1,args...);
}

int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
//assic value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space
ll power(ll x,ll n){ll result=1;while(n>0){if(n%2==1)result=(result*x)%mod; x=((x%mod)*(x%mod))%mod;n=n/2;}return result;}

string s,t;
int cache[3005][3005];
int n,m;

int dp(int i, int j){
    if(i>=n || j>=m) return 0;
    int &ans=cache[i][j];
    if(ans!=-1) return ans;
    ans=0;
    if(s[i]==t[j]) ans=max(ans,dp(i+1,j+1)+1);
    else ans=max(dp(i+1,j),dp(i,j+1));
    return ans;
}

void path(int i, int j){
    if(i>=n || j>=m) return;
    ll ans=dp(i,j);
    if(s[i]==t[j]){
        cout << s[i];
        return path(i+1,j+1);
    }
    else{
        if(ans==dp(i+1,j)) return path(i+1,j);
        else path(i,j+1);
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> s;
    cin >> t;
    n=s.size();
    m=t.size();
    mst(cache,-1);
    int res=dp(0,0);
    path(0,0);
    return 0;
}

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

int main() {
    int N;
    cin >> N;
    
    int count = 0;
    for (int i = 0; i < N; i++) {
        int l, r;
        cin >> l >> r;
        count += r - l + 1;    
    }
    
    cout << count << endl;
}

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

int main(){
    string s,t,u;
    cin >> s >> t;
    int a,b;
    cin >> a >>b;
    cin >> u;

    if(u==s){
        cout << a-1 <<" "<<b<<endl;
    }else{
        cout << a<<" "<<b-1<<endl;
    }

}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << endl;
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

struct mint {
    ll x; // typedef long long ll;
    mint(ll x=0):x((x%MOD+MOD)%MOD){}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += MOD-a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return pow(MOD-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};

ostream& operator << (ostream& os, const mint a) {
    os << a.x;

    return os;
}

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

const int NMAX = int(1e7);
ll fact[NMAX+1], finv[NMAX+1], inv[NMAX+1];

void comb_init(int N) {
    // init
    REP(i, 2) {
        fact[i] = 1;
        finv[i] = 1;
        inv[i] = 1;
    }

    FOR(i, 2, N+1) {
        fact[i] = fact[i-1] * i % MOD;
        inv[i] = MOD - MOD / i * inv[MOD % i] % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}

mint comb(int n, int k) {
    if (n < k || n < 0 || k < 0) return 0;

    return mint(fact[n]) * finv[k] * finv[n-k];
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int K;
    cin >> K;

    string S; cin >> S;

    comb_init(K + S.size() + 10);

    mint ans = 0;
    REP(k, K + 1) {
        mint c = comb(S.size() + k - 1, k);
        ans += c * mint(25).pow(k) * mint(26).pow(K - k);
    }

    print(ans);
    
}


Measured memory_bytes: 51172
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <tuple>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <numeric>
#include <string.h>
#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define repn(i, x) for (int i = 1; i <= (int)(x); i++)
#define repr(i, x) for (int i = ((int)(x) - 1); i >= 0; i--)
#define reprn(i, x) for (int i = ((int)(x)); i > 0; i--)
#define all(x) (x).begin(),(x).end()
typedef long long int64;
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const long long INFL = 1e18;
const int MOD = 1000000007;
const int MAX = 210000;

int gcd(int a, int b) {
    return b != 0 ? gcd(b, a % b) : a;
}

//逆元を求める関数
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
      fac[i] = fac[i-1] * i % MOD;
      inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
      finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
//組み合わせ
long long COM (int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

void solve() {
		string s; cin >> s;
		int n; n = 13;
		vector<int64> dp(n);
		//dp[k] -> 13で割った余りがkのパターン数(今の状態)
		//余りが0は必ず存在するので1をカウントする
		dp[0] = 1;
		int mul = 1;
		//後ろからカウントする
		//3 -> >?3 -> 2?3のように遷移する
		for (int i = s.length() - 1; i >= 0; --i) {
			//次の状態
			vector<int64> next_dp(n);
			char c = s[i];
			if (c  == '?') {
				//文字が?である場合は0〜9まで遷移させる
				for (int k = 0; k < 10; ++k) {
					//各桁について、13の余りを全て加算して次の桁の余りのパターンをカウントする
					for (int j = 0; j < n; ++j) {
						next_dp[(k * mul  + j) % n] += dp[j];
						next_dp[(k * mul  + j) % n] %= MOD;
					}
				}
			} else {
				int k = (int)(c  - '0');
				for (int j = 0; j < n; ++j) {
					next_dp[(k * mul  + j) % n] += dp[j];
					next_dp[(k * mul  + j) % n] %= MOD;
				}
			}
			mul *= 10;
			mul %= n;
			dp = next_dp;
		}
		cout << dp[5] << endl;
    return;
}

int main() {
    solve();
    return 0;
}



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

#define rep(i, n) for(int i=0; i<n; ++i)
#define repit(it, li) for(auto it=li.begin(); it!=li.end(); it++)
#define ll long long int

int main(){
   string s;
   cin>>s;
   string hi="hi";
   bool ok=true;
   if(s.size()%2==0){
      rep(i, s.size()){
         if(s[i]!=hi[i%2]) ok=false;
      }
   }
   else ok=false;
   cout << (ok?"Yes":"No") << endl;
   return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
const int N=100005;
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
ll n;
vector<ll>ans(N,0);
vector<pii>ar;
int main()
{ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;cin>>x;ar.push_back({x,-i});
    }
    sort(ar.begin(),ar.end());
    reverse(ar.begin(),ar.end());
    ll mn=-ar[0].second;
    ll pr=ar[0].first;
    ll cnt=0;
    for(auto el:ar){
        auto vl=el.first;
        auto p=-el.second;
        if(pr!=vl){
            //cout<<mn<<' '<<vl<<' '<<pr<<' '<<cnt<<' '<<ans[mn]<<'\n';
            ans[mn]+=(pr-vl)*cnt;
            pr=vl;
        }
        cnt++;
        mn=min(mn,p);


    }
    ans[1]+=pr*n;
    for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
    return 0;
}


Measured memory_bytes: 6108
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

N, M = map(int, input().split())
tree = UnionFind(N)

for _ in range(M):
    fr, to, _ = map(int, input().split())
    tree.union(fr - 1, to - 1)

print(tree.getComponent())


Measured memory_bytes: 8564
#include <iostream>
using namespace std;
int main() {
	string S, T, U;
	int A, B;

	cin >> S >> T;
	cin >> A >> B;
  	cin >> U;
  
  	if(S == U) {
      A--;
    }else if(T == U) {
      B--;
    }
  
	cout << A << " " << B <<endl;
   
	return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int alphabet[26];

int main() {
	char Input;

	while (cin >> Input) {
		if ('a' <= Input&&Input <= 'z')
			alphabet[Input - 'a']++;
		else if ('A' <= Input&&Input <= 'Z')
			alphabet[Input - 'A']++;
	}

	for (char i = 0; i < 26; i++) {
		cout << (char)('a' + i) << " : " << alphabet[i] << endl;
	}

	return 0;
}

Measured memory_bytes: 1140
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=205,mod=998244353;
int n,ans,fastpow[N],x[N],y[N];
int main(){
	scanf("%d",&n);
	fastpow[0]=1;
	for(int i=1;i<=n;i++){
		scanf("%d%d",&x[i],&y[i]);
		fastpow[i]=1LL*fastpow[i-1]*2%mod;
	}
	ans=(fastpow[n]-n-n*(n-1)/2-1)%mod;
	for(int i=1;i<=n;i++){
		for(register int j=i+1;j<=n;j++){
			int tot=0;
			for(register int k=j+1;k<=n;k++){
				if((x[i]-x[j])*(y[j]-y[k])==(y[i]-y[j])*(x[j]-x[k])){
					tot++;
				}
			}
			ans=(ans-fastpow[tot]+1)%mod;
		}
	}
	printf("%d\n",(ans+mod)%mod);
	return 0;
}

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

using namespace std;

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

  if (N == 0) {
    cout << 0 << endl;
    return 0;
  }

  vector<int> S;
  long long now = 0;
  long long m = 2;
  long long k = 1;
  while (now != N) {
    int s = (N - now) % m != 0;
    S.push_back(s);
    if (s) now += k;
    m *= 2;
    k *= -2;
  }
  int sz = S.size();
  for (int i = sz - 1; i >= 0; i--) {
    cout << S[i];
  }
  cout << endl;

  return 0;
}
/* vim:set fdm=marker: */


Measured memory_bytes: 256
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 1e5 + 10;
int a[N];
int b[N];
int c[N];
LL sum[N];
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	for (int i = 1; i <= n; i++) cin >> c[i];
	sort(a + 1, a + n + 1);
	sort(b + 1, b + n + 1);
	sort(c + 1, c + n + 1);
	for (int i = 1; i <= n; i++)
	{
		int pos = upper_bound(c + 1, c + n + 1, b[i]) - c;
		sum[i] = n - pos + 1;
	}
	for (int i = n; i >= 1; i--) sum[i] += sum[i + 1];
	LL ans = 0;
	for (int i = 1; i <= n; i++)
	{
		int pos = upper_bound(b + 1, b + n + 1, a[i]) - b;
		ans += sum[pos];
	}
	cout << ans << endl;
	return 0;
}


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

// #define int long long // intで書いたけど心配なときにlong longに変換する
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)
#define X real()
#define Y imag()

/* REPmacro */
#define REPS(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (ll i = (a); i >= (ll)(n); --i)
#define DEP(i, n) DEPS(i, n, 0)
#define EACH(i, n) for (auto&& i : n)

/* debug */
#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

/* alias */
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using plglg = pair<ll, ll>;
using tlglglg = tuple<ll, ll, ll>;
using D = double;
using P = complex<D>;
using vs = vector<string>;
template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;
const D EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

/* func */
inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
inline int in() {int x; cin >> x; return x;}
inline ll IN() {ll x; cin >> x; return x;}
inline vs split(const string& t, char c) {vs v; stringstream s(t); string b; while(getline(s, b, c)) v.eb(b); return v;}
template <typename T> inline bool chmin(T& a, const T& b) {if (a > b) a = b; return a > b;}
template <typename T> inline bool chmax(T& a, const T& b) {if (a < b) a = b; return a < b;}
template <typename T, typename S> inline void print(const pair<T, S>& p) {cout << p.first << " " << p.second << endl;}
template <typename T> inline void print(const T& x) {cout << x << endl;}
template <typename T, typename S> inline void print(const vector<pair<T, S>>& v) {for (auto&& p : v) print(p);}
template <typename T> inline void print(const vector<T>& v, string s = " ") {REP(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}
inline void yesno(bool ok, string yes = "Yes", string no = "No") {cout << (ok?yes:no) << endl;}


signed main() {
    //my-code
    string s; cin >> s;
    ll d = 0;
    REP(i, s.length()) {
        d += (ll)(s[i] - '0');
    }

    if (d % 9 == 0) {
        print("Yes");
    } else {
        print("No");
    }

    return 0;
}

// https://github.com/kurokoji/.cpp-Template/wiki テンプレートについて
// http://www.creativ.xyz/dump-cpp-652 dump()について
// https://gist.github.com/rigibun/7905920 色々

Measured memory_bytes: 3728
using System;
class _0018
{
    public static void Main()
    {
        string[] snum = Console.ReadLine().Split();
        int[] num = new int[snum.Length];
        for (int i = 0; i < num.Length; i++) num[i] = int.Parse(snum[i]);
        Array.Sort(num);
        Array.Reverse(num);
        Console.Write(num[0]);
        for (int i = 1; i < num.Length; i++) Console.Write(" " + num[i]);
        Console.Write("\n");
    }
}

Measured memory_bytes: 5748
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let mut iter = buf.split_whitespace();

    let h: usize = iter.next().unwrap().parse().unwrap();
    let n: usize = iter.next().unwrap().parse().unwrap();

    let mut sum: usize = 0;
    for _ in 0..n {
        sum = sum + iter.next().unwrap().parse::<usize>().unwrap();
    }
    if sum >= h {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     @hamayanhamayan0
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/














int N;
string S[101010];
vector<string> v = { "AC", "WA", "TLE", "RE" };
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> S[i];

	map<string, int> C;
	rep(i, 0, N) C[S[i]]++;

	fore(x, v) printf("%s x %d\n", x.c_str(), C[x]);
}







Measured memory_bytes: 6900
#pragma region template
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD = 1e9 + 7, MAX = 1e18, larg = 1e5, INF = -1e9;
long long A, B, C, D, E, F, G, H, I, J, K, L, N, M, O, P, Q, R, S, T, U, V, W, x, y, z;
long long max_value = INF, max_index = -1;
long long min_value = MAX, min_index = -1;
typedef long long ll;
typedef pair<ll, ll> Pa;

template <std::int_fast64_t Modulus> class modint {
	using u64 = std::int_fast64_t;
public:
	u64 a;
	constexpr modint(const u64 x = 0) noexcept : a(x% Modulus) {}
	constexpr u64& value() noexcept { return a; }
	constexpr const u64& value() const noexcept { return a; }
	constexpr modint operator+(const modint rhs) const noexcept {
		return modint(*this) += rhs;
	}
	constexpr modint operator-(const modint rhs) const noexcept {
		return modint(*this) -= rhs;
	}
	constexpr modint operator*(const modint rhs) const noexcept {
		return modint(*this) *= rhs;
	}
	constexpr modint operator/(const modint rhs) const noexcept {
		return modint(*this) /= rhs;
	}
	constexpr modint& operator+=(const modint rhs) noexcept {
		a += rhs.a;
		if (a >= Modulus) {
			a -= Modulus;
		}
		return *this;
	}
	constexpr modint& operator-=(const modint rhs) noexcept {
		if (a < rhs.a) {
			a += Modulus;
		}
		a -= rhs.a;
		return *this;
	}
	constexpr modint& operator*=(const modint rhs) noexcept {
		a = a * rhs.a % Modulus;
		return *this;
	}
	constexpr modint& operator/=(modint rhs) noexcept {
		u64 exp = Modulus - 2;
		while (exp) {
			if (exp % 2) {
				*this *= rhs;
			}
			rhs *= rhs;
			exp /= 2;
		}
		return *this;
	}
};
#pragma endregion

typedef modint<MOD> m;
m func[400001];
void funcinit(int N)
{
	func[0] = 1;
	for (int i = 1; i <= N; i++)
	{
		func[i] = func[i - 1] * i;
	}
}
m comb(m n, m r)
{
	if (n.a <= 0 || n.a < r.a)
	{
		return 0;
	}
	return func[n.a] / (func[r.a] * func[(n - r).a]);
}

int num[3] = { 0 };
bool exist[3] = { false };
int main() {
	cin >> N >> M;
	bool flag = true;
	rep(i, M) {
		cin >> A >> B;
		if (exist[A - 1] && num[A - 1] != B) flag = false;
		num[A - 1] = B;
		exist[A - 1] = true;
	}
	if (!flag) cout << -1;
	else {
		if (num[0] == 0 && N != 1 && exist[0]) {
			cout << -1;
			return 0;
		}
		if (!exist[0] && N != 1) num[0] = 1;
		rep(i, N) {
			cout << num[i];
		}
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ll n,k,j;
	cin>>n>>k;
	ll arr[n],i,dp[k+1],x;
	for(i=0;i<=k;i++)
		dp[i]=0;
	for(i=0;i<n;i++)
		cin>>arr[i];
	sort(arr,arr+n);//0 == lose   1 == win
	dp[arr[0]]=1;
	for(i=arr[0];i<=k;i++)
	{
		for(j=0;j<n;j++)
		{
			x=i-arr[j];
			if(x<0 || dp[i])
				j=n;
			else
				dp[i]=1-dp[i-arr[j]];
		}
	}
	if(dp[k])
		cout<<"First"<<endl;
	else
		cout<<"Second"<<endl;
	return 0;
}

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

int main()
{
  int N,M;
  cin >> N;
  vector<int> vec1(N);
  vector<int> vec2(N);
  M = 0;
  for (int i = 0; i < N; i++)
  {
    cin >> vec1.at(i) >> vec2.at(i);
  }
  
  for(int i = 0;i < N;i++)
  {
    if(vec1.at(i) == vec2.at(i))
    {
      M += 1;
      if(M >=3)
      {
        break;
      }
    }
    else
    {
      M = 0;
    }
  }
  if(M >= 3)
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3624
using System;
using System.Linq;

class Amondai
{
    static void Main()
    {
        var line = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
        var A = line[0];
        var B = line[1];
        Console.WriteLine(B%A==0?A+B:B-A);
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/integer/common_factor.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

using std::string;
using std::vector;
using std::set;
using std::multiset;
using std::unordered_set;
using std::map;
using std::multimap;
using std::unordered_map;
using std::pair;
using std::cin;
using std::cout;

using boost::multiprecision::cpp_int;
using cpp_dec_float_1000 = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1000>>;

typedef uintmax_t    ull;
typedef intmax_t     ll;
typedef uint64_t     ul;
typedef uint32_t     ui;
typedef uint8_t      uc;

constexpr char CRLF  = '\n';
constexpr char SPACE = ' ';
constexpr char VECTOR_COUT_SEPARATOR = SPACE;
constexpr ll INF = 1000'000'007;
constexpr int MOD = 1000'000'007;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> std::ostream& operator<< (std::ostream& os, const std::vector<T>& vc) { for(auto it = vc.begin(); it != vc.end(); ++it) { if (std::next(it) == vc.end()) os << *it; else os << *it << VECTOR_COUT_SEPARATOR; } return os; }
template<class T1, class T2> inline std::ostream & operator<< (std::ostream & os, const std::pair<T1, T2> & p) { return os << p.first << ' ' << p.second; }
template<class T> T modinv(T a, T m) { T b = m, u = 1, v = 0; while (b) { T t = a / b; a -= t * b; boost::swap(a, b); u -= t * v; boost::swap(u, v); } u %= m; if (u < 0) u += m; return u; }
template<class T> inline bool isSosuu(const T& n) { if (n == T(1)) { return false; } for (T i = 2; i*i <= n; ++i) { if (n % i == 0) { return false; } } return true; }
template<class T> vector<vector<T>> split (const vector<T>& S, T delim) { vector<vector<T>> ret{}; vector<T> buff{}; for (auto c : S) { if (c == delim) { if (!buff.empty()) ret.push_back(buff); buff.clear(); } else { buff.push_back(c); } } if (!buff.empty()) ret.push_back(buff); return ret; }

struct Tmp
{
public:
  Tmp(int N);
};

Tmp::Tmp(int N){}

void solve(void)
{
  string s, t; cin >> s >> t;
  auto cmp = [](const string& s, const string& t) {
    int m = std::min(s.size(), t.size());
    for (int i = 0; i < (int)m; ++i) {
      if (s[i] != t[i]) {
        return s[i] < t[i];
      }
    }
    if (s.size() != t.size()) {
      return s.size() < t.size();
    } else {
      return false;
    }
  };
  boost::sort(s, std::less<char>());
  boost::sort(t, std::greater<char>());
  auto ans = cmp(s, t);
  cout << (ans ? "Yes" : "No") << CRLF;
  return;
}

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

  solve();

  return 0;
}


Measured memory_bytes: 256
N=int(input())
S=str(input())

def count(index,Set):
    if index in Set:
        return 1
    else:
        return 0

L=[[],[],set()]
for x in range(N):
    if S[x]=='R':
        L[0].append(x)
    elif S[x]=='G':
        L[1].append(x)
    else:
        L[2].add(x)

number=len(L[2])

ans=0
for i in L[0]:
    for j in L[1]:
        if (i+j)%2==0:
            m=(i+j)//2
            res1=number-count(m,L[2])-count(2*i-j,L[2])-count(2*j-i,L[2])
            ans+=max(0,res1)
        else:
            res2=number-count(2*i-j,L[2])-count(2*j-i,L[2])
            ans+=max(0,res2)

print(ans)



Measured memory_bytes: 9316
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		try(final Scanner sc = new Scanner(System.in)){
			final int N = sc.nextInt();
			
			long[] as = new long[N];
			long[] abs = new long[N];
			long sum = 0;
			for(int i = 0; i < N; i++) {
				as[i] = sc.nextLong();
				abs[i] = Math.abs(as[i]);
				sum += abs[i];
			}
			
			for(int i = 0; i < N - 1; i++) {
				if(as[i] < 0) { 
					as[i] *= -1; as[i + 1] *= -1;
				}else if(as[i] == 0 && as[i + 1] < 0) {
					as[i] *= -1; as[i + 1] *= -1;
				}
			}
			
			int cnt = 0;
			for(int i = 0; i < N; i++) {
				if(as[i] < 0) { cnt++; }
			}
			
			final long min = Arrays.stream(abs).min().getAsLong();
			System.out.println(sum - (cnt > 0 ? 2 * min : 0));
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}

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

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define REPV(iter, v) for(auto (iter)=(v).begin(); (iter)!=(v).end();++(iter))
#define ALL(v) (v).begin(),(v).end()

#define MOD 1000000007

using namespace std;

typedef long long ll;

int main()
{
    ll N, A, B;
    cin >> N >> A >> B;

    string ans = (B - A) % 2 == 0 ? "Alice" : "Borys";

    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
inline int_fast64_t read(){int_fast64_t x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;}
inline string read_s(){string s="";char c=getchar();while(c<'!'||c>'~'){c=getchar();}while(c>='!'&&c<='~'){s+=c;c=getchar();}return s;}
void Main(){
    int r = read();
    printf("%d\n", r*r*3);
}
int main(){cin.tie(nullptr);ios::sync_with_stdio(false);Main();return 0;}

Measured memory_bytes: 256
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

using namespace std;

template<typename T, class Predicate>
T partition_point_num(T left, T right, Predicate pred)
{
    while(left <= right) {
        T mid = (left + right) / (T)2;

        if (pred(mid)) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return left;
}

/**
   ceil(0, 2) == 0
   ceil(1, 2) == 1
   ceil(2, 2) == 1
   ceil(3, 2) == 2
   ceil(4, 2) == 2
*/
template<class T>
T ceil(T dividend, T divisor)
{
    return (dividend + (divisor - 1)) / divisor;
}

int main()
{
    int64_t N, A, B;
    std::cin >> N >> A >> B;

    std::vector<int64_t> H;
    for (decltype(N) i = 0; i < N; ++i) {
        int64_t t;
        std::cin >> t;
        H.push_back(t);
    }

    std::sort(std::begin(H), std::end(H),
              [](const auto& a, const auto& b) {
                  return a > b;
              });

    const int64_t M = N * *std::max_element(H.begin(), H.end()) / B;
    auto ans =
        partition_point_num<int64_t>(int64_t(1), M,
                                     [&H, A, B, N](auto n) -> bool {
                                         int64_t count = 0;
                                         for (int64_t i = 0; i < N; ++i) {
                                             if (H[i] <= B*n) {
                                                 break;
                                             }
                                             count += ceil(H[i] - B*n, A - B);
                                         }
                                         return n < count;
                                     });
    std::cout << ans<< std::endl;

    return 0;
}


Measured memory_bytes: 1400
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int R = sc.nextInt();
		String contest;
		if (R < 1200) {
			contest = "ABC";
		} else if (R < 2800) {
			contest = "ARC";
		} else {
			contest = "AGC";
		}
		System.out.println(contest);
	}
}

Measured memory_bytes: 20820
#include<bits/stdc++.h>
using namespace std;
#define int long long
#undef int
#define mk make_pair
#define pb push_back
typedef pair<int, int> pii;
const int mod = 1000000007;
const int INF = 1000000009;
const long long INFL = 1000000000000000018ll;

string s;
int K;

signed main()
{
    cin >> s >> K;
    int N = s.size();
    int A = 'z' + 1;
    for(int i = 0; i < N; i++){
        if(s[i] == 'a')continue;
        if(K >= A - s[i]){
            K -= (A - s[i]);
            s[i] = 'a';
        }
    }
    s[N - 1] = 'a' + (s[N - 1] - 'a' + K) % 26;
    cout << s << endl;

    return 0;
}

/*



*/


Measured memory_bytes: 512
using System;

namespace v0_0005
{
    class Program
    {
        static void Main(string[] args)
        {
            string line;
            while (!string.IsNullOrEmpty(line = Console.ReadLine()))
            {
                var ab = line.Split(' ');
                var a = int.Parse(ab[0]);
                var b = int.Parse(ab[1]);
                int LCM = 1;
                int GCD = 1;

                int divVal;
                while ((divVal = GetDivisor(a, b)) != -1)
                {
                    a /= divVal;
                    b /= divVal;
                    GCD *= divVal;
                }
                LCM = GCD * a * b;

                Console.WriteLine("{0} {1}", GCD, LCM);
            }
        }

        static int GetDivisor(int a, int b)
        {
            for (int i = 2; i <= Math.Max(a, b); i++)
            {
                if ((a % i == 0) && (b % i == 0))
                {
                    return i;
                }
            }
            return -1;
        }
    }
}

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

typedef long long ull;
const ull modConst = 1E9 + 7;

ull facMemo[2000005];
ull fastExp(ull A, ull B)
{
	if(B == 0)
		return 1 % modConst;
		
	ull Sqrt = fastExp(A, B / 2), ans = (Sqrt * Sqrt) % modConst;
	if(B % 2 == 1)
		ans *= A % modConst;
		
	return ans % modConst;
}

ull modInverse(ull X)
{
	return fastExp(X, modConst - 2);
}

ull choose(int N, int R)
{
	if(N < R)
		return 0;
		
	ull ans = (facMemo[N] * modInverse(facMemo[N - R])) % modConst;
	ans = (ans * modInverse(facMemo[R])) % modConst;
	
	return ans;
}

int main()
{
	ull K;
	scanf("%lld", &K);
	
	string S;
	cin >> S;
	
	facMemo[0] = 1 % modConst;
	for(ull i = 1; i < 2000005; i++)
		facMemo[i] = (facMemo[i - 1] * i) % modConst;
	
	ull ans = 0, sLen = (ull)(S.length());
	for(ull i = 0; i <= K; i++)
	{
		ull numLettersPart1 = K - i, numLettersPart2 = i;
		
		ull part1 = (choose(numLettersPart1 + sLen - 1, numLettersPart1) * fastExp(25, numLettersPart1)) % modConst;
		ull part2 = fastExp(26, numLettersPart2);
		
		ans += (part1 * part2) % modConst;
		ans %= modConst;
	} 
	
	printf("%lld", ans);
}


Measured memory_bytes: 20140
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;
 
int main() {
    int H, W, M; scanf("%d%d%d", &H, &W, &M);
    vector< vector<int> > rows(H), cols(W);
    for(int i=0; i<M; i++) {
        int h, w; scanf("%d%d", &h, &w);
        h--; w--;
        rows[h].emplace_back(w);
        cols[w].emplace_back(h);
    }

    vector<int> nums(W);
    set< pair<int, int> > rec_cols;
    for(int i=0; i<W; i++) {
        rec_cols.emplace(cols[i].size(), i);
        nums[i] = cols[i].size();
    }

    int ans = 0;
    for(int i=0; i<H; i++) {
        for(auto c : rows[i]) {
            rec_cols.erase(make_pair(nums[c], c));
            nums[c]--;
            rec_cols.emplace(make_pair(nums[c], c));
        }

        chmax(ans, (int)(rows[i].size() + rec_cols.rbegin()->first));

        for(auto c : rows[i]) {
            rec_cols.erase(make_pair(nums[c], c));
            nums[c]++;
            rec_cols.emplace(make_pair(nums[c], c));
        }
    }
    printf("%d\n", ans);
    return 0;
}


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

int main(){
    int h, w;
    cin >> h >> w;
    int c[10][10];
    rep(i, 10) rep(j, 10) cin >> c[i][j];
    rep(k, 10) rep(i, 10) rep(j, 10) c[i][j] = min(c[i][j], c[i][k]+c[k][j]);
    
    int cnt = 0;
    rep(i, h){
        rep(j, w){
            int a; cin >> a;
            if(a!=-1) cnt += c[a][1];
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
n = input()

l = len(n)

ans = 0
j = 1
for i in range(1, l, 2):
    ans += 9 * j
    j *= 100

if l % 2 == 0:
    print(ans)
else:
    ans += (int(n[0]) - 1) * j
    if l != 1:
        ans += int(n[1:]) + 1
    else:
        ans += 1
    print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

int main() {
  int n, a, b, c, d;
  string s;
  cin >> n >> a >> b >> c >> d;
  cin >> s;
  a--;
  b--;
  c--;
  d--;
  s += '#';

  auto find_range = [&](const string& t, int l, int r) {
    auto sub = s.substr(l, r - l + 1 - t.length() + 1);
    if (sub.find(t) == string::npos) return false;
    return true;
  };

  if (find_range("##", b, d) || find_range("##", a, c)) {
    cout << "No" << endl;
    return 0;
  }
  if (c < d) {
    cout << "Yes" << endl;
    return 0;
  }

  bool ok = false;
  for (int i = b; i <= d; i++) {
    if (s[i - 1] == '.' && s[i] == '.' && s[i + 1] == '.') ok = true;
  }
  if (ok) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3768
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define println(x) cout << x << endl;
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    if (a <= 5 ){
        println(0);
    }
    else if (a <= 12 ){
        println(b/2);
    }
    else {
        println(b);
    }
    return 0;
}

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

typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int N, K;
double E[200000];
double ans = 0;

int main(){
  cin >> N >> K;
  rep(i, N){
    int p;
    cin >> p;
    E[i] = p + 1;
  }
  rep(i, K){
    ans = ans + E[i];
  }
  int sum = ans;
  rep(i, N - K){
    //cout << sum <<endl;
    sum = sum - E[i] + E[i + K];
    if(sum > ans) ans = sum;
  }
  ans = ans / 2;
  printf("%lf",ans);
}
  

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
static const ll MAX = pow(10, pow(10, 10));

int main()
{
    int Q;
    scanf("%d", &Q);
    for (int i = 0; i < Q; i++)
    {
        ll A, B;
        scanf("%lld %lld", &A, &B);
        ll C = sqrt(A * B);
        ll count = 0;

        if ( A > B) swap(A, B);

        if (C * (C + 1) < A * B)
        {
            count += C * 2; 
        }
        else
        {
            --C;
            count += C * 2 ;
            if ( (C + 1) * (C + 1) < A * B && (C + 1) != A)
            {
                count++;
            }

        }
        
        if ( C >= A ) count--;

        printf("%lld\n", count);
    }
    
    return 0;
}

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

const int MAX_N = 1e5 + 1;

ll D[MAX_N], P[MAX_N];

void solve(int N, int M) {
    map<int, int> cnt;
    vector<int> exp_value(N);
    for (int i = 0; i < N; i++) {
        cin >> D[i] >> P[i];
        cnt[P[i]] += D[i];
        exp_value[i] = P[i];
    }
    sort(exp_value.begin(), exp_value.end());
    exp_value.erase(unique(exp_value.begin(), exp_value.end()), exp_value.end());
    reverse(exp_value.begin(), exp_value.end());
    for (int i = 0; i < exp_value.size(); i++) {
        if (M >= cnt[exp_value[i]]) {
            M -= cnt[exp_value[i]];
            cnt[exp_value[i]] = 0;
        }
        else {
            cnt[exp_value[i]] -= M;
            M = 0;
        }
    }
    int ans = 0;
    for (auto i = cnt.begin(); i != cnt.end(); i++) {
        if (i->second == 0) continue;
        ans += i->first * i->second;
    }
    cout << ans << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    while (true) {
        cin >> N >> M;
        if (N == 0 && M == 0) break;
        solve(N, M);
    }
    return 0;
}


Measured memory_bytes: 3216
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

int n;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    cout << (n - 2) * 180 << endl;
}


Measured memory_bytes: 256