akhauriyash/Code-Regression huggingface dataset:
{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE BangPatterns #-}

import           Control.Applicative
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import qualified Data.ByteString.Char8       as B
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import           Data.Function
import           Data.List
import           Data.Primitive.MutVar
import           Data.Tuple
import qualified Data.Vector                 as V
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM

main :: IO ()
main = do
    [v, e] <- map read.words <$> getLine
    edges <- U.unfoldrN e (readInt2.B.dropWhile isSpace) <$> B.getContents
    putStr.unlines.map showEdge . solve . fromEdges v $ toUndirectedEdges edges

solve :: Graph -> [Edge]
solve gr = sort $ bridges gr

type Vertex = Int
type Edge = (Vertex, Vertex)
type Graph = V.Vector (U.Vector Vertex)

showEdge :: Edge -> String
showEdge (src, dst) = shows src " " ++ show dst

toUndirectedEdges :: U.Vector Edge -> U.Vector Edge
toUndirectedEdges edges = edges U.++ U.map swap edges

fromEdges :: Int -> U.Vector Edge -> Graph
fromEdges numV edges = V.map U.fromList
    . V.unsafeAccumulate (flip (:)) (V.replicate numV [])
    $ U.convert edges

nothing :: Int
nothing = -1

bridges :: Graph -> [Edge]
bridges gr = runST $ do
    let numV = V.length gr
    low <- UM.replicate numV nothing
    num <- UM.replicate numV nothing
    parent <- UM.replicate numV nothing
    bridge <- newMutVar [] :: ST s (MutVar s [Edge])
    numOfVisited <- newMutVar 0 :: ST s (MutVar s Int)

    let root = 0

    fix `flip` root `flip` nothing $ \dfs !v !p -> do
        !nv <- readMutVar numOfVisited
        modifyMutVar' numOfVisited (+1)
        UM.unsafeWrite num v nv
        UM.unsafeWrite parent v p
        UM.unsafeWrite low v nv

        U.forM_ (V.unsafeIndex gr v) $ \child -> do
            isVisited <- (/= nothing) <$> UM.unsafeRead num child
            if not isVisited
            then do
                dfs child v
                lc <- UM.unsafeRead low child
                unsafeModify low v (min lc)
                when (nv < lc) $
                    modifyMutVar' bridge ((min v child, max v child):)
            else
                when (child /= p) $ do
                    nc <- UM.unsafeRead num child
                    unsafeModify low v (min nc)

    readMutVar bridge

-------------------------------------------------------------------------------

readInt2 :: B.ByteString -> Maybe ((Int,Int), B.ByteString)
readInt2 bs = Just ((x,y),bsy)
  where
    Just (x, bsx) = B.readInt bs
    Just (y, bsy) = B.readInt $ B.unsafeTail bsx

unsafeModify :: (PrimMonad m, GM.MVector mv a)
             => mv (PrimState m) a -> Int -> (a -> a) -> m ()
unsafeModify v i f = GM.unsafeRead v i >>= GM.unsafeWrite v i . f
{-# INLINE unsafeModify #-}

Measured memory_bytes: 14712
import java.util.Scanner;

public class Main {

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        String s = "";
        for(int i=0; i<3; i++) {
            s += sc.next();
        }
        System.out.println("" + s.charAt(0) + s.charAt(4) + s.charAt(8));
    }

}


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

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

#define rep(i, N) for (ll i = 0; i < (N); i++)
#define FOR(i, a, b) for (ll i = (a), i < (N): i++)
#define all(A) (A).begin(), (A).end()

int main(){
    int N;
    cin >> N;
    int tmp = 0;
    int n = N;
    rep(i, 8) {
        tmp += n % 10;
        n /= 10;
    }
    if (N % tmp == 0) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }


    return 0;
}


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

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    rep(i,n) cin >> h[i];

    int ans = 0;
    rep(i,n) {
        if (k <= h[i]) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 764
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 998244353;
const long long INF = 1e18;
typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> PLL;
typedef pair<LD, LL> pdl;
typedef pair<LD, LD> pdd;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned long long ULL;
//typedef boost::multiprecision::cpp_int bigint;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	LL N;
	cin >> N;
	VLL childs(N,0);
	for (LL n = 1; n < N; n++) {
		LL a;
		cin >> a;
		childs[a - 1]++;
	}
	for (LL n = 0; n < N; n++) {
		cout << childs[n] << "\n";
	}
	return 0;
}


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

struct BIT{
    int N;
    vector<int> dat;
    BIT() {}
    BIT(int n) {
		N = n;
		dat.resize(N + 1);
    }
    // update k th element (0-index)
	void add(int k, int x){
        k++;
		while(k <= N){
			dat[k] += x;
			k += k&-k;
		}
	}
	// sum [0, k) (0-index)
	int sum(int k){
		int s = 0;
		while(k > 0){
			s += dat[k];
			k -= k&-k;
		}
		return s;
	}
	// sum [a, b) (0-index)
	int query(int a, int b){
		return sum(b) - sum(a);
	}
};

int main(){
    int n, q;
    cin >> n >> q;
    BIT b(n);
    for(int i = 0; i < q; i++){
        int com, x, y;
        cin >> com >> x >> y;
        if(com == 0){
            x--;
            b.add(x, y);
        }else if(com == 1){
            x--; y--;
            // cout << b.sum(y + 1) << ' ' << b.sum(x) << endl;
            cout << b.query(x, y + 1) << endl;
        }
    }
}

/* verified
https://onlinejudge.u-aizu.ac.jp/#/courses/library/3/DSL/all/DSL_2_B
*/


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

int main(){
  int n,m,o[100];
  string b[100];
  string l;
  int ans;

  for(;;){
    cin >> n >> m;
    if(!n && !m)break;

    ans = 0;
    for(int i=0;i<n;i++)cin >> b[i] >> o[i];
    for(int i=0;i<m;i++){
      cin >> l;
      for(int j=0;j<n;j++){
	bool f = true;
	for(int k=7;k>=0;k--){
	  if(b[j][k] != '*' && b[j][k] != l[k]){
	    f = false;
	    break;
	  }
	}
	if(f){
	  ans += o[j];
	  break;
	}
      }
    }

    cout << ans << endl;
  }
}

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

#define IOS ios::sync_with_stdio(false); cin.tie(0);
using Int64 = long long;

class UnionFind {
private:
    vector<int> par;
    vector<int> siz;

public:
    UnionFind(int n) : par(n+1) ,siz(n+1) {
        for(int i = 1; i <= n ; i++) {
            par[i] = i;
            siz[i] = 1;
        }
    }

    int root(int x) {
        return par[x] == x ? x: par[x] = root(par[x]);
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    void marge(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        // サイズの大きい方につける
        if (siz[x] < siz[y]) swap(x,y);
        siz[x] += siz[y];
        par[y] = x;
        return;
    }

    int size(int x) {
        return siz[root(x)];
    }
};

int main(void) {
    int N,M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    for(int i = 0; i < M; i++) cin >> A[i] >> B[i];

    UnionFind uf(N);
    Int64 cur = (Int64) N * (N-1) / 2;
    vector<Int64> res;
    for(int i = 0;i < M; i++) {
        res.push_back(cur);

        int a = A[M-1-i];
        int b = B[M-1-i];
        if (uf.same(a,b)) continue;

        Int64 sa = uf.size(a);
        Int64 sb = uf.size(b);
        cur -= sa * sb;
        uf.marge(a,b);
    }

    reverse(res.begin(), res.end());

    for(Int64& l : res) cout << l << endl;

}


Measured memory_bytes: 3828
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

	Scanner sc=new Scanner(System.in);

	int INF=1<<28;
	double EPS=1e-9;

	int n;
	int[] m, a, b;

	void run(){
		for(;;){
			n=sc.nextInt();
			if(n==0){
				break;
			}
			m=new int[n];
			a=new int[n];
			b=new int[n];
			for(int i=0; i<n; i++){
				m[i]=sc.nextInt();
				a[i]=sc.nextInt();
				b[i]=sc.nextInt();
			}
			solve();
		}
	}

	void solve(){
		for(int j=0; j<n; j++){
			int sum1=0, sum2=0;
			for(int i=0; i<n; i++){
				if(a[i]<=a[j]&&a[j]<b[i]){
					sum1+=m[i];
				}
				if(a[i]<=b[j]-1&&b[j]-1<b[i]){
					sum2+=m[i];
				}
			}
			if(sum1>150||sum2>150){
				println("NG");
				return;
			}
		}
		println("OK");
	}

	void debug(Object... os){
		System.err.println(Arrays.deepToString(os));
	}

	void print(String s){
		System.out.print(s);
	}

	void println(String s){
		System.out.println(s);
	}

	public static void main(String[] args){
		// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		new Main().run();
	}
}

Measured memory_bytes: 13000
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
using namespace std;
int mn=207,n;
int main(){
	cin>>n;
	for (int i=1;i<=n;++i){
		int t=0,a;
		cin>>a;
		while (a%2==0)t++,a/=2;
		mn=min(mn,t);
	}
	printf("%d\n",mn);
	return 0;
}

Measured memory_bytes: 256
# import math
# import decimal
# import queue
# import bisect
# import heapq
# import time
# import itertools

mod = int(1e9+7)

def main():
    a,b = map(int,input().split())
    if a+b==15:
        print('+')
    elif a*b==15:
        print('*')
    else:
        print('x')
    return

if __name__=='__main__':
    main()

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

int main() {
    int n, sum = 0;
    cin >> n;
    
    vector<int> d(n);
    
    rep(i, n) cin>>d[i];
    
    for(int i = 0;i<n;i++){
        for(int j = i+1;j<n;j++) sum += d[i]*d[j];
        
    }
    
    cout<<sum<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
int main() {

	long long n,ans = 0,waru = 10; cin >> n;
	if (n % 2 != 0) { cout << "0" << endl; }
	else {

		for (int i = 1; ; i++) {
			if (waru > n) { break; }
			ans += n / waru;
			waru *= 5;
		}

		cout << ans << endl;
	
	}

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>

using namespace std;

#define rep(i, start, end) for (int i = (int)(start); i < (int)(end); i++)
#define charToInt(c) c - 'a'

int main(int argc, const char *argv[])
{

    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;

    //０、もしくは１が連続する区間の長さを管理
    vector<int> ranges0;
    vector<int> ranges1;

    //後述の計算を簡単にするため、ダミーの区間を追加
    if(s[0] == '0')
    {
        ranges1.push_back(0);
    }

    {
        
        int i, j = 0;
        for (i = 0, j = i + 1; j < s.length(); j++)
        {
            if (s[i] != s[j])
            {
                if(s[i] == '0')
                {

                    ranges0.push_back(j - i);
                }
                else
                {
                    ranges1.push_back(j - i);
                }
                
                i = j;
            }
        }

        //最後の区間を追加
        if(s[s.length() - 1] == '0')
        {

            ranges0.push_back(j - i);
        }
        else
        {
            ranges1.push_back(j - i);
        }
    }
    
    //後述の計算を簡単にするため、ダミーの区間を追加
    if(s[n-1] == '0')
    {
        ranges1.push_back(0);
    }

    //0の区間をk個含むように連続する区間を計算
    //0の区間を最大まで含むように合計するには
    //1の区間1,0の区間1,1の区間2,0の区間2,...,1の区間k,0の区間k,1の区間(k+1)
    //の2k+1個の区間を合計するのが最大。
    //ただし、sが0から始まる場合はの区間1が、0で終わる場合は1の区間(k+1)がない可能性があるため
    //最初と最後にダミーを追加する

    //先に最初の2k+1個の区間を計算しておく
    long long int total = 0;
    {
        int i = 0;
        int ubi = min(k, (int)ranges0.size());
        for(i=0;i<ubi;i++)
        {
            total += ranges1[i];
            total += ranges0[i];
        }

        total += ranges1[ubi];
    }

    //0の区間の個数がk個以下の場合は全てを0に変えることができる
    if((int)ranges0.size() <= k)
    {
        cout << total << endl;
        return 0;
    }
    

    long long int total_max = total;
    for(int i=0;i<ranges0.size() - k;i++)
    {
        //i=0の時、total = r1[0] + r0[0] + r1[1] + r0[1] + ... + r1[k-1] + r0[k-1] + r1[k]
        //i=1の時、total =                 r1[1] + r0[1] + ... + r1[k-1] + r0[k-1] + r1[k] + r0[k] + r1[k+1]
        //なので、次の和を計算するときは最初の２項を引いて最後の２項を足す
        total -= ranges1[i];
        total -= ranges0[i];
        total += ranges0[i+k];
        total += ranges1[i+k+1];
        
        if(total_max < total) total_max = total;
    }
    
    cout << total_max << endl;

    return 0;
}


Measured memory_bytes: 1020
n=gets.to_i
s=gets.chomp

r=s.count("R")
w=s.count("W")
ans=[r,w].min
w=0

(n-2).times do |i|
    if s[i]=="W"
        w+=1
    else
        r-=1
    end
    ans=[ans,[w,r].max].min
end

puts ans


Measured memory_bytes: 14744
#include<bits/stdc++.h>
using namespace std;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V))

vector<string> split(string,string);

//template<typename T>
//void swap(T*,T*);
//char ToUpper (char cX) { return toupper(cX); }

int main()
{
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if(a+b == c+d)
    {
        cout << "Balanced";
    }
    else if(a+b >c+d)
    {
        cout << "Left";
    }else
    {
        cout <<"Right";
    }
}


Measured memory_bytes: 256
A,B,M=map(int,input().split())
a=list(map(int,input().split()))#冷蔵庫値段
b=list(map(int,input().split()))#電子レンジ
xyc=[list(map(int,input().split())) for i in range(M)]
#x番目の冷蔵庫、y番目のレンジを買うとc円割引される

min_a=min(a)
min_b=min(b)
ans=min_a+min_b

for x,y,c in xyc:
    temp=a[x-1]+b[y-1]-c
    if temp<ans:ans=temp
print(ans)

Measured memory_bytes: 38488
#include <string>
#include <vector>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <map>
using namespace std;


#define prec(i) cout << fixed << setprecision(i)

const long long int MOD = 1000000007;

long long int fact(long long int k) {
	long long int sum = 1;
	for (long long int i = 2; i <= k; i++)
		sum *= i;

	return sum;
}

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

long long int power(int a, int b) {
	long long int  ans = 1;
	for (int i = 0; i < b; i++)
		ans = (ans * a) % MOD;

	return ans;
}


int main()
{
	long long int x, sum = 0;

	cin >> x;

	if (ceil((x % 100) / 5.0) <= x / 100)
		cout << 1 << endl;
	else
		cout << 0 << endl;


	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<queue>	

using namespace std;

namespace MyLib {
#define ALL(a) a.begin(),a.end()
#define REP(i,n) for(int i=0;i<n;i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define debug(x) if(1)cout<<#x<<":"<<x<<endl;
#define DEBUG(x) if(1)cout<<#x<<":"<<x<<endl;
#define ll long long
}

using namespace MyLib;
bool ju[21][21];
int rx[30], ry[30];


int main() {
	int m;
	int l[30];
	char buf;

	int x, y;
	int n;
	while (cin >> n, n) {
		REP(i, 21)
			REP(j, 21)
			ju[i][j] = 0;
		REP(i, n)
			cin >> x >> y, ju[y][x] = 1;
		cin >> m;
		REP(i, m) {
			cin >> buf >> l[i];
			if (buf == 'E') {
				rx[i] = 1;
				ry[i] = 0;
			}
			else if (buf == 'W') {
				rx[i] = -1;
				ry[i] = 0;
			}
			else if (buf == 'N') {
				rx[i]= 0;
				ry[i] = 1;
			}
			else if (buf == 'S') {
				rx[i] = 0;
				ry[i] = -1;
			}

		}
		x = 10, y = 10;
		int count = 0;
		REP(i,m)
			REP(j, l[i]) {
				x += rx[i];
				y += ry[i];
				if (ju[y][x]) {
					ju[y][x] = 0;
					count++;
				}
		}
		if (count == n)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}

	return 0;

}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
#define double long double
using namespace std;

ll kol, x;
ll top = 100;

int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> x;
    while (top < x)
    {
        top = (ll)(top * 1.01);
        kol ++;
    }
    cout << kol;
    return 0;
}


Measured memory_bytes: 3652
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

ans = 0
for i in range(n):
    d = min(a[i],b[i])
    ans += d
    a[i] -= d
    b[i] -= d
    d = min(a[i+1],b[i])
    ans += d
    a[i+1] -= d
    b[i] -= d

print(ans)


Measured memory_bytes: 97476
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
const long long mod = 1e9+7;
//////////////////////////////////

int main() {
  int n, m; cin >> n >> m;
  vector<int> h(n);
  for(int i=0; i<n; i++) cin >> h[i];
  vector<vector<int>> d(n);
  int a, b;
  for(int i=0; i<m; i++) {
    cin >> a >> b;
    a--; b--;
    d[a].push_back(b);
    d[b].push_back(a);
  }

  vector<bool> f(n, true);
  int cnt = 0;
  for(int i=0; i<n; i++) {
    if (!f[i]) continue;

    bool x = true;
    for(int j=0; j<d[i].size(); j++) {
      if (h[i] <= h[d[i][j]]) {
        x = false;
        break;
      } else {
        f[d[i][j]] = false;
      }
    }
    if (x) cnt++;
  }
  cout << cnt << endl;


  return 0;
}

// EOF


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

using namespace std;

const int INF=1e9;

int main (){
	int n,k;
	cin >> n >> k;
	vector<int> h(n);
	vector<int> dp(n,INF);
	dp[0]=0;
	for(int i=0; i<n; ++i) cin >> h[i];
	for(int i=0; i<n; ++i){
		for(int j=1; j<=k && i+j<n; ++j) {
			dp[i+j]=min(dp[i+j],dp[i]+abs(h[i]-h[i+j]));
		}
	}
	cout << dp[n-1];
				
	return 0;
}



Measured memory_bytes: 3960
#include <stdio.h>
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>

int main(){
  
  // read problem
  char s[100001], t[100001];
  long long int s_len, t_len;
  scanf("%s", s);
  scanf("%s", t);
  s_len = strlen(s);
  t_len = strlen(t);
  
  std::vector< std::vector<long long int> > s2_list(26);
  for(int i = 0; i < s_len; i++){
    s2_list[(int)s[i] - 'a'].push_back(i);
  }
  for(int i = 0; i < s_len; i++){
    s2_list[(int)s[i] - 'a'].push_back(i+s_len);
  }
  
  // solve probelm
  long long int sprime_len = 0;
  long long int current_index = s_len-1;
  long long int difference;
  int flag = 1;
  
  for(long long int i = 0; i < t_len; i++){
    if(s2_list[(int)t[i] - 'a'].size() == 0){
      flag = 0;
      break;
    }
    
    difference = *(std::upper_bound(s2_list[(int)t[i]-'a'].begin(), s2_list[(int)t[i]-'a'].end(), current_index)) - current_index;
    sprime_len += difference;
    current_index += difference;
    current_index %= s_len;
  }
  
  if(flag==0){
    std::cerr << "Answer:" << std::endl;
    std::cout << "-1" << std::endl;
  }
  else{
    std::cerr << "Answer: " << std::endl;
    std::cout << sprime_len << std::endl;
  }
  
  return 0;
}



Measured memory_bytes: 2680
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 190;

int n, m;
char s[N][N];
int sum[N][N];
int dp[N][N][N], tmp[N][N][N];

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif

  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i)
    scanf("%s", s[i] + 1);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      sum[i][j] = (s[i][j] == '#') + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
  for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j) {
      int l = 0;
      for (int k = 1; k <= m; ++k) {
        ++l;
        while (true) {
          int expect = (j - i + 1) * l, actual = sum[j][k] - sum[j][k - l] - sum[i - 1][k] + sum[i - 1][k - l];
          if (actual == 0 || actual == expect)
            break;
          --l;
        }
        dp[i][j][k] = l;
      }
    }
  int ans = 0;
  while (dp[1][n][m] != m) {
    ++ans;
    memset(tmp, 0, sizeof(tmp));
    for (int i = 1; i <= n; ++i) {
      for (int k = 1; k <= m; ++k) {
        int ptr = i;
        for (int j = i + 1; j <= n; ++j) {
          while (ptr < j - 1 && dp[i][ptr + 1][k] > dp[ptr + 2][j][k])
            ++ptr;
          tmp[i][j][k] = max(min(dp[i][ptr][k], dp[ptr + 1][j][k]), min(dp[i][ptr + 1][k], dp[ptr + 2][j][k]));
        }
      }
    }
    for (int i = 1; i <= n; ++i)
      for (int j = i; j <= n; ++j)
        for (int k = m; k; --k)
          dp[i][j][k] = max(tmp[i][j][k], dp[i][j][k] + dp[i][j][k - dp[i][j][k]]);
  }
  printf("%d\n", ans);

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}


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


int main(){
  int A,B,C,D;
  int count=0;

  cin >> A >> B >> C >> D;
  if(A<=C && B>=C){
    if(B<=D)count = B - C;
    else count =D-C;
  }
  else if(A>=C && D>=A){
    if(D<=B) count = D-A;
    else count = B-A;
  }
  cout << count << endl;

}

Measured memory_bytes: 256
#include<stdio.h> 
#include<algorithm>
using namespace std;
int main(){
	int a,b,c,d,i;
	scanf("%d%d%d",&a,&b,&c);
	for(i=1;i<=min(a,b);i++){
		if(a%i==0&&b%i==0)
			d=i;
	}
	if(c%d)
		printf("NO\n");
	else
		printf("YES\n");
	return 0;
}

Measured memory_bytes: 128
// Standard I/O
#include <iostream>
#include <sstream>
#include <cstdio>
// Standard Library
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
// Template Class
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
// Container Control
#include <algorithm>

using namespace std;

#define rep( i, n ) for( int i = 0; i < n; ++i )
#define irep( i, n ) for( int i = n-1; i >= 0; --i )
#define reep( i, s, n ) for ( int i = s; i < n; ++i )
#define ireep( i, n, s ) for ( int i = n-1; i >= s; --i )
#define foreach(itr, x) for( typeof(x.begin()) itr = x.begin(); itr != x.end(); ++itr)

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all( v ) v.begin(), v.end()
#define fs first
#define sc second
#define vc vector

// for visualizer.html
double SCALE = 1.0;
double OFFSET_X = 0.0;
double OFFSET_Y = 0.0;
#define LINE(x,y,a,b) cerr << "line(" << SCALE*(x) + OFFSET_X << ","	\
	<< SCALE*(y) + OFFSET_Y << ","										\
	<< SCALE*(a) + OFFSET_X << ","										\
	<< SCALE*(b) + OFFSET_Y << ")" << endl;
#define CIRCLE(x,y,r) cerr << "circle(" << SCALE*(x) + OFFSET_X << ","	\
	<< SCALE*(y) + OFFSET_Y << ","										\
	<< SCALE*(r) << ")" << endl;

typedef long long ll;
typedef complex<double> Point;

typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector< vector<int> > vii;
typedef vector< vector<double> > vdd;

typedef vector<int>::iterator vi_itr;

const int IINF = 1 << 28;
const double INF = 1e30;
const double EPS = 1e-10;
const double PI = acos(-1.0);

// Direction : L U R D
const int dx[] = { -1, 0, 1, 0};
const int dy[] = { 0, -1, 0, 1 };

int main()
{
	string str;
	cin >> str;

	cout << str.substr(0, 4) + " " + str.substr(4) << endl;
}


Measured memory_bytes: 760
import java.util.Scanner;

public class Main {

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

		int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt(), d = sc.nextInt();
		int ans = Math.min(b, d) - Math.max(a, c);
		System.out.println(ans > 0 ? ans : 0);

		sc.close();
	}
}


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

void solve(long long X)
{
    cout << 1000 * (X / 500) + 5 * ((X % 500) / 5) << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    long long X;
    scanf("%lld", &X);
    solve(X);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define uniq(v) v.erase(unique(v.begin(),v.end()),v.end())
#define lb(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define ub(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
const ll mod=1000000007;
//const ll mod=998244353;
const ld pi=acos(-1.0);
const ll INF = 1LL<<61;
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; }
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; }
ll jou(ll N, ll P){if(P==0) return 1;
  if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
  }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる



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

  int d;
  cin>>d;

  vector<ll> p(26);
  rep(i,26) {
    cin>>p[i];
  }


  vector<vector<ll>> q(d,vector<ll>(26));
  rep(i,d) {
    rep(j,26) {
      cin>>q[i][j];
    }
  }

  ll pre=0;
  vector<int> r(26,0);
  rep(i,d-5){
    ll ans=-INF;
    ll memo;
    rep(j,26){
      ll sum=pre;
      auto last=r;
      sum+=q[i][j];
      last[j]=i+1;
      rep(k,26){
        sum-=5*p[k]*(i+1-last[k])/2;
      }
      if(sum>ans) {
        memo=j;
        chmax(ans,sum);
      }
    }
    cout << memo+1 << endl;
    pre=ans;
    r[memo]=i+1;
  }

  ll answer=-INF;
  ll A,B,C,D,E;
  vector<int> zen(5);
  rep(i,26){
    rep(j,26){
      rep(k,26){
        rep(l,26){
          rep(m,26){
            zen[0]=i;
            zen[1]=j;
            zen[2]=k;
            zen[3]=l;
            zen[4]=m;

            ll sum=0;
            auto last=r;
            rep(n,5){
              sum+=q[d-5+n][zen[n]];
              last[zen[n]]=d-5+n+1;
              rep(o,26){
                sum-=p[o]*(d-5+n+1-last[o]);
              }
            }

            if(sum>answer) {
              A=zen[0];
              B=zen[1];
              C=zen[2];
              D=zen[3];
              E=zen[4];
            }
            chmax(answer,sum);

          }
        }
      }
    }
  }

  cout << A+1 << endl;
  cout << B+1 << endl;
  cout << C+1 << endl;
  cout << D+1 << endl;
  cout << E+1 << endl;
  
}

Measured memory_bytes: 3724
N, Q = map(int, input().split())
S = list(input())

mark = [0]*(N+1)

for i in range(2, N+1):
    if S[i-2] == 'A' and S[i-1] == 'C':
        mark[i] = mark[i-1] + 1
    else:
        mark[i] = mark[i-1]

for i in range(Q):
    l,r = map(int,input().split())
    l = l - 1
    r = r - 1
    print(mark[r+1]-mark[l+1])

Measured memory_bytes: 8512
import java.util.*;


public class Main {
	public static void main (String[] args){
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int N = sc.nextInt();
		int A = 0;
		for(int n = 0; n < N; n++) {
			A += sc.nextInt();
		}
		if(A >= H) {
			System.out.println("Yes");
		}
		else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 48068
#include <bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long n,s;
long long a[3005];
long long dp[3005][3005];
int main(){
	cin>>n>>s;
	for(int i=0;i<n;++i){
		cin>>a[i];
	}
	dp[0][0]=1;
	for(int i=0;i<n;++i){
		for(int j=0;j<=s;++j){
			dp[i+1][j]+=2*dp[i][j];
			dp[i+1][j]%=mod;
			if(j+a[i]<=s){
				dp[i+1][j+a[i]]+=dp[i][j];
				dp[i+1][j+a[i]]%=mod;
			}
		}
	}
	cout<<dp[n][s]<<'\n';
	return 0;
}

Measured memory_bytes: 74068
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    char c[1010];
    scanf("%s", c);
    
    // 2. あだ名を作成.
    string ans = "";
    rep(i, 3) ans.pb(c[i]);
    
    // 3. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

Measured memory_bytes: 3668
#include<stdio.h>

void merge(int a[], int left, int mid, int right){
    int i = left; int j = mid+1; int k = 0;
    int b[right-left+1];

    while( i <= mid && j <= right){
        if(a[i] <= a[j]){
            b[k] = a[i]; i++;
        } else {
            b[k] = a[j]; j++;
        }
        k++;
    }

    if(i == mid+1){
        while(j <= right){
            b[k] = a[j]; j++; k++;
        } 
    } else {
        while(i <= mid){
            b[k] = a[i]; i++; k++;
        }
    }

    for(i = 0; i < k; i++){
        a[i+left] = b[i];
    }
}

void merge_sort(int a[], int left, int right){
    if(left == right) return ;

    int mid = (left+right)/2;
    merge_sort(a, left, mid);
    merge_sort(a, mid+1, right);
    merge(a, left, mid, right);
}

int main()
{
    int N, K, i;
    fscanf(stdin, "%d %d", &N, &K);

    int p[N];
    for(i = 0; i < N; i++){
        fscanf(stdin, "%d", &p[i]);
    }

    merge_sort(p, 0, N-1);

    int dif;
    int min_dif = p[K-1] - p[0];
    for(i = 1; i <= N-K; i++){
        dif = p[i+K-1] - p[i];
        if(min_dif > dif){
            min_dif = dif;
        }
    }
    
    fprintf(stdout, "%d\n", min_dif);
    return 0;
}

Measured memory_bytes: 896
n=int(input())
a=list(map(int, input().split()))

stock=0
money=1000
#極小は-1、極大は1、何もしないは0
graph=[0]*n
if a[0]<a[1]:
    graph[0]=-1
    increase=1
elif a[0]==a[1]:
    increase=0
else:
    increase=-1

for i in range(1,n-1):
    #株価上昇中
    if increase==1:
        if a[i]>a[i+1]:
            graph[i]=1
            increase=-1
    #株価下落中
    if increase==-1:
        if a[i]<a[i+1]:
            graph[i]=-1
            increase=1
    #横ばい
    if increase==0:
        if a[i]<a[i+1]:
            graph[i]=-1
            increase=1
        if a[i]>a[i+1]:
            graph[i]=1
            increase=-1

if a[n-2]<a[n-1]:
    graph[n-1]=1

for i in range(n):
    if graph[i]==-1:
        stock=money//a[i]
        money-=a[i]*stock
    if graph[i]==1:
        money+=a[i]*stock
        stock=0
if stock>0:
    money += a[n-1]*stock
    
print(money)

Measured memory_bytes: 9212
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:108777216")
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <utility>
#include <algorithm>
#include <ctime>
using namespace std;
int s[100000];

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	
	int n;
	scanf("%d", &n);
	int sum = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d", &s[i]);
		sum += s[i];
	}
	double min_df = 1e100;
	int ind = 0;
	for (int i = 0; i < n; i++) {
		double val = fabs(s[i] - (sum / (double)n));
		if (val < min_df) {
			min_df = val;
			ind = i;
		}
	}
	cout << (ind);
	return 0;
}

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


int main(){
  int h,w;
  cin >> h >> w;
  vector<string> c(h);
  for(int i=0;i<h;++i){
    cin >> c[i];
  }
  for(int i=0;i<h;++i){
    for(int k=0;k<2;++k){
      cout << c[i] << endl;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue> //std::priority_queue<int, vector<int>, less<int>> que; // 4, 3, 2, 1 (defualt, less) : 
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm> // std::sort(begin(),end()) // 0, 1, 2, 3 ,4 (default, less);
#include <numeric>  // std::accumulate(m.begin(), m.end(), 0LL);
#include <functional>
#include <cassert>
#include <cctype>  // std::islower(), std::isupper(), std::tolower, std::toupper
#include <iomanip> // std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

int main (void) {
  std::string s, t; std::cin >> s >> t;
  std::unordered_map<char, std::vector<ll>> Table;
  for(unsigned int i=0; i<s.size(); i++) Table[s[i]].push_back(i);

  // check
  for(unsigned int j=0; j<t.size(); j++) {
    if ( Table.count(t[j]) == 0 ) {
      std::cout << -1 << std::endl;
      return 0;
    }
  }


  ll ans = 0;
  ll nowpos = 0;
  ll befpos = -1;
  const ll length = s.size();
  for(unsigned int j=0; j<t.size(); j++) {
    char now = t[j];
    auto rtn = std::upper_bound(Table[now].begin(), Table[now].end(), befpos);
    if ( j == 0 ) {
      ans = (*rtn);
      nowpos = (*rtn);
      befpos = nowpos;
      continue;
    }
    if ( rtn == Table[now].end() ) {
      nowpos = Table[now][0];
      ans += (ll)((ll)Table[now][0]+length-befpos);
    }
    else {
      nowpos = (*rtn);
      ans += (ll)((ll)(*rtn) - (ll)befpos);
    }
    befpos = nowpos;
  }
  std::cout << ans + 1 << std::endl;

  return 0;
}


Measured memory_bytes: 1724
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin >> S;
  if(S == "Sunny")cout << "Cloudy" << endl;
  if(S == "Cloudy")cout << "Rainy" << endl;
  if(S == "Rainy")cout << "Sunny" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const int MAX_N = 60;

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

vector<int> par;
vector<int> rnk;
int root;

void init(int n){
    par = vector<int>(n);
    rnk = vector<int>(n);
    root = n;
    for (int i = 0; i < n; i++){
        par[i] = i;
        rnk[i] = 0;
    }
}

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

void unite(int x, int y){
    x = find(x);
    y = find(y);
    if (x == y) return;

    if (rnk[x] < rnk[y]) par[x] = y;
    else{
        par[y] = x;
        if (rnk[x] == rnk[y]) par[y] = x;
    }

    root--;
}

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

int a[MAX_N], b[MAX_N], g[MAX_N][MAX_N];

int main(){
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        a[i] = x - 1;
        b[i] = y - 1;
        g[x - 1][y - 1] = 1;
    }

    int ans = 0;
    for (int i = 0; i < m; i++){
        init(n);
        g[a[i]][b[i]] = 0;
        for (int j = 0; j < m; j++){
            if (g[a[j]][b[j]]) unite(a[j], b[j]);
        }

        for (int k = 0; k < n; k++){
            if (!same(a[i], k)){
                ans++;
                break;
            }
        }
        g[a[i]][b[i]] = 1;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
// JOI 2010-2011 予選6
#include<iostream>
#include<cstring>

const int mod = 100000;

int M, N;
char flag[20][20];
// dp[crt or nxt][直前N文字において隣接する2列の文字がJOか][直前の1つがJか(次にJOが来るか判定するため)]
int dp[2][1 << 20][2];
char JOI[4] = "JOI";

int main()
{
	std::cin >> M >> N;
	for( int i = 0; i != M; ++i )
		for( int j = 0; j != N; ++j )
			std::cin >> flag[i][j];

	dp[0][0][0] = 1;

	int crt = 0, nxt = 1;

	for( int i = 0; i != M; ++i )
	{
		for( int j = 0; j != N; ++j )
		{
			memset( dp[nxt], 0, sizeof( dp[nxt] ) );

			for( int bit = 0; bit != 1 << N; ++bit )
			{
				for( int f = 0; f != 2; ++f )
				{
					if( dp[crt][bit][f] )
					{
						for( int k = 0; k != 3; ++k )
						{
							if( flag[i][j] != '?' && flag[i][j] != JOI[k] )
								continue;
							if( bit >> j & 1 && JOI[k] == 'I' )
								continue;

							int nbit = bit & ~( 1 << j ), nf = JOI[k] == 'J';
							if( f && JOI[k] == 'O' )
								nbit |= 1  << ( j - 1 );

							dp[nxt][nbit][nf] += dp[crt][bit][f];
							if( dp[nxt][nbit][nf] >= mod )
								dp[nxt][nbit][nf] -= mod;
						}
					}
				}
			}

			std::swap( crt, nxt );
		}

		for( int bit = 0; bit != 1 << N; ++bit )
		{
			dp[crt][bit][0] += dp[crt][bit][1];
			if( dp[crt][bit][0] >= mod )
				dp[crt][bit][0] -= mod;

			dp[crt][bit][1] = 0;
		}
	}

	int ans = 1;
	for( int i = 0; i != M; ++i )
		for( int j = 0; j != N; ++j )
			if( flag[i][j] == '?' )
				ans = ( ans * 3 ) % mod;

	for( int i = 0; i != 1 << N; ++i )
		ans = ( ans + mod - dp[crt][i][0] ) % mod;

	std::cout << ans << std::endl;

	return 0;
}

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

#define all(x) begin(x), end(x)

using i64 = int_fast64_t;
using f64 = double;
using p64 = pair<i64, i64>;

constexpr i64 INF = INT_FAST64_MAX / 2;
constexpr f64 EPS = DBL_EPSILON;

void solve() {
    i64 n;
    cin >> n;
    vector<i64> a(3 * n);
    for (auto& e : a) cin >> e;
    sort(all(a), greater<>());
    i64 ans = 0;
    for (i64 i = 0; i < n; i++) ans += a[2 * i + 1];
    cout << ans << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


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

struct Node{
    int key;
    struct Node *prev,*next;
};


struct Node *nil;//node???????????¨????°?

void trace(){
    struct Node *n;
    n=nil->next;
    cout << n->key;
    n = n->next;
    while(n!=nil){
        cout<<" "<<n->key;
        n = n->next;
        if(n==nil)break;
    }
    cout << endl;
}

void init(){
    nil =(struct Node *)malloc(1*sizeof(struct Node));
    nil->prev = nil;
    nil->next = nil;
}

void insert(int key){
    struct Node *node = (struct Node *)malloc(1*sizeof(struct Node));
    node -> key = key;
    node -> next = nil->next;
    nil->next->prev = node;
    nil->next = node;
    node -> prev = nil;
    //trace();
}

void deleteNode(struct Node* node){
    if(node==nil)return;
    /*??????????????????????????????????????¨?????????????????????*/
    node->prev->next = node->next;
    node->next->prev = node->prev;
    free(node);
}

void deleteFirst(){
    deleteNode(nil->next);
}

void deleteLast(){
    deleteNode(nil->prev);
}

struct Node* listSearch(int key) {
    struct Node *n = nil->next;
    while(n != nil && n->key != key ) {
        n = n-> next;
    }
    return n;
}

void deleteKey(int key) {
    deleteNode(listSearch(key));
    //trace();
}

// void deleteKey(int key){
//     struct Node *n;
//     n = nil->next;
//     while(n->key!=key && n!=nil){
//         //cout << "??°???" << n << endl;
//         n = n->next;
//         //cout << "??°??????" << n << endl;
        
//     }
//     delete(n);
//     trace();
// }




int main(){
    init();
    int n,key;
    string command;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> command;
        if(command=="insert"){
            cin >> key;
            insert(key);
        }else if(command=="delete"){
            cin >> key;
            deleteKey(key);           
        }else if(command=="deleteFirst"){
            deleteFirst();
            continue;
        }else if(command=="deleteLast"){
            deleteLast();
            continue;
        }
    }
    
    trace();
    
    return 0;
}

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

using namespace std;
#define ll long long int
int const mod=1000000007;
int main()
{
    ll n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    sort(a,a+n);
    ll ans=a[n-1];
    ll x=n-2;
    for(int i=n-2;i>=0;i--)
    {
        if(x>=2)
        {
            ans+=2*a[i];
        x-=2;
        }
        else if(x==1)
        {
            ans+=a[i];
            x--;
        }
        if(x==0)
            break;
    }
    cout<<ans;
}


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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

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

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


int main() {
    i64 H, W, N; cin >> H >> W >> N;
    using P = pair<i64, i64>;
    set<P> black;
    REP(i, N) {
        i64 a, b; cin >> a >> b;
        a--, b--;
        black.emplace(a, b);
    }

    map<i64, i64> dist;
    set<P> used;
    dist[0] = (H - 2) * (W - 2);

    auto count = [&](i64 y, i64 x) {
        i64 cnt = 0;
        for (i64 dy = 0; dy <= 2; dy++) {
            for (i64 dx = 0; dx <= 2; dx++) {
                i64 cy = y + dy;
                i64 cx = x + dx;
                if (cy < 0 || cy >= H || cx < 0 || cx >= W) return 0L;
                cnt += black.count({cy, cx});
            }
        }
        return cnt;
    };
    for (const auto [y, x] : black) {
        for(i64 dy = 0; dy >= -2; dy--) {
            for(i64 dx = 0; dx >= -2; dx--) {
                i64 cy = y + dy;
                i64 cx = x + dx;
                if (cy < 0 || cy >= H || cx < 0 || cx >= W) continue;
                if (used.count({cy, cx}) > 0) continue;
                used.insert({cy, cx});
                dist[count(cy, cx)]++;
                dist[0]--;
            }
        }
    }

    REP(i, 10) {
        cout << dist[i] << endl;
    }

    return 0;
}


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

typedef long long int ll;
typedef long double ld;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define MOD (ll)(1e9 + 7)
#define vi vector<int>
#define vii vector<vector<int> >
#define vl vector<ll>
#define vll vector<vector<ll> >
#define vc(T, nm) vector<T> nm
#define pb push_back
#define popb pop_back
#define si set<int>
#define sl set<ll>
#define F first
#define S second
#define pii pair<int, int>
#define mp make_pair
#define ins insert
#define ers erase
#define endl "\n"
#define mul(a, b) ((a % MOD) * (b % MOD)) % MOD
#define adr(a, b) ((a % MOD) + (b % MOD)) % MOD
#define FORA(x, s, e, inc) for(ll x = s; x != e; x += inc)
#define ROFA(x, s, e, inc) for(ll x = s; x != e; x -= inc)
#define FOR(x, s, e) FORA(x, s, e, 1)
#define ROF(x, s, e) ROFA(x, s, e, 1)
#define loop(x, n) FOR(x, 0, n)
#define rd1(t, a) 					t a; cin >> a;
#define rd2(t, a, b) 				rd1(t, a); rd1(t, b); 
#define rd3(t, a, b, c) 			rd2(t, a, b); rd1(t, c);
#define rd4(t, a, b, c, d) 			rd3(t, a, b, c); rd1(t, d);
#define rd5(t, a, b, c, d, e) 		rd4(t, a, b, c, d); rd1(t, e);
#define rd6(t, a, b, c, d, e, f) 	rd5(t, a, b, c, d, e); rd1(t, f);
#define rdA(t, nm, len)				t nm[len]; loop(i, len) {cin >> nm[i];}
#ifdef DEBUG
	#define deb(v) cout << endl << #v << ": " << v << endl
	#define db1(v) cout << endl << #v << ": " << "[ "; for(auto x: v) {cout << x << " ";}; cout << "]" << endl;
	#define db2(v) cout << endl << #v << ": " << endl; for(auto r: v) {cout << "[ "; for(auto x: r) {cout << x << " ";}; cout << "]" << endl;};
	#define dbl cout << "-------------------------------" << endl
#else
	#define deb(v)
	#define db1(v)
	#define db2(v)
	#define dbl
#endif

void solve() {
    rd1(ll, x);
    ll cv = 100, time = 0;
    while(cv < x) {
        cv += (ll)(0.01 * cv);
        time++;
    }
    cout << time;
}

int main() {
	
	fastio;

// 	rd1(ll, t);
	ll t = 1;

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



	return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define DUMP(x)  cout << #x << " = " << (x) << endl;
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define IFOR(i, m, n) for(ll i = n - 1; i >= m; i-- )
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
#define FOREACH(x,a) for(auto& (x) : (a) )
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) ll(x.size())
void no(){
  cout << -1 << endl;
  exit(0);
}

int main(){
  ll N; cin >> N;
  vector<ll> a(N);
  REP(i,N) cin >> a[i];
  if(a[0]>0) no();
  ll ans = 0;
  REP(i,N-1){
    if(a[i+1] > a[i]+1) no();
    if(a[i+1] <= a[i]) ans += a[i];
  }
  ans += a[N-1];
  cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>
using namespace std;
int main(void){
    long long x,cnt = 0,ans = 0;
    cin >> x;
    
    ans = (x / 11) * 2;
    cnt = x % 11;
    
    if(cnt >= 1 && cnt <= 6) ans++;
    else if(cnt >= 7) ans += 2;
 
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int N,M;
struct state{
  int t,l,id;
  bool operator<(const state& st) const {
    if( t == st.t ) return l>st.l;
    return t > st.t;
  }
  bool operator>(const state& st) const {
    if( t == st.t ) return l<st.l;
    return t < st.t;
  }
  state(int t,int l,int id) : t(t),l(l),id(id){}
  state(){}
};
int main(){
  while( cin >> N >>M &&(N|M) ) {
    priority_queue<state> sp;
    for(int i=0;i<N;i++){
      int a; cin >> a;
      int tmp = a;
      state gp;
      if( sp.empty() ) gp = state(M,10000,-1);      
      else gp = sp.top();
      while( state(a,tmp,(i+1)) > gp && a < M ) a+=tmp;
      if( a > M ) a -= tmp;
      sp.push( state( a, tmp, i+1 ) );
    }
    state res = sp.top(); sp.pop();
    bool f = false;
    while( !sp.empty() ){
      state p = sp.top(); sp.pop();
      if( res.t == p.t && res.l == p.l ) f = true;
      // cout << res.t << " "<< res.l <<" " << res.id << endl;
      //cout << p.t << " "<< p.l <<" " << p.id << endl;
    }
    if( f ) cout << N << endl;
    else cout << res.id << endl;
  }
}

Measured memory_bytes: 1224
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <numeric> // accumulate(v.begin(), v.end(), 0)                                                         

using namespace std;
#define ll long long

int main(){
  int N;
  cin >> N;
  vector<int> A;
  for(int i=0; i<N; i++){
    int in;
    cin >> in;
    A.push_back(in);
  }
  sort(A.begin(), A.end(), greater<int>());
  int alice = 0, bob = 0;
  for(int i=0; i<N; i++){
    if(i % 2 == 0)
      alice += A[i];
    else
      bob += A[i];
  }
  cout << alice - bob << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N; cin >> N;
  vector<int> h(N);
  if(N==1){
    cout << "Yes" << endl;
    return 0;
  }
  for(int i=0;i<N;i++){
    cin >> h.at(i);
  }
  for(int i=N-1;i>0;i--){
    if(h.at(i)+1<h.at(i-1)){
      cout << "No" << endl;
      return 0;
    }
    if(h.at(i)+1==h.at(i-1)){
      h.at(i-1)--;
    }
  }
  cout << "Yes" << endl;
}

Measured memory_bytes: 640