akhauriyash/Code-Regression huggingface dataset:
n = gets.to_i
ans = Array.new(n+1).map{[0,0,0]}
n.times do |i|
    a,b,c = gets.split.map(&:to_i)
    ans[i+1][0] = (ans[i][1] > ans[i][2] ? ans[i][1] : ans[i][2])+a
    ans[i+1][1] = (ans[i][2] > ans[i][0] ? ans[i][2] : ans[i][0])+b
    ans[i+1][2] = (ans[i][0] > ans[i][1] ? ans[i][0] : ans[i][1])+c
end
puts ans[n].max

Measured memory_bytes: 10108
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
A = III()

d = defaultdict(list)
for i in range(N):
    d[A[i]].append(i)

ans = 1
val = 3
for i in range(max(d.keys())+1):
    if len(d[i])>val:
        print(0)
        exit()
    else:
        if i==0:
            before = d[i]
            val = len(d[i])
        else:
            x = []
            for k in d[i]:
                x.append(sum([k>b for b in before]))
            z = 1
            for j,x1 in enumerate(x):
                z *= max(x1-j,0)
            if z==0:
                print(0)
                exit()
            else:
                ans *= z
                ans %= mod
            before = d[i]
m = 0
for x in d.values():
    if len(x)>=m:
        m = len(x)
if m==1:
    ans *= 3
    ans %= mod
else:
    ans *= 6
    ans %= mod

print(ans)

Measured memory_bytes: 69868
// #define _GLIBCXX_DEBUG
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<int, int>; using vi = vector<int>; using vvi = vector<vi>; using pll = pair<ll, ll>; using vl = vector<ll>; using vvl = vector<vl>; using vb = vector<bool>; using vvb = vector<vb>;
#define rep0(TMS) for (int CNT = 0; CNT < (int)(TMS); CNT++)
#define rep(CNT, GOAL) for (int CNT = 0; CNT < (int)(GOAL); CNT++)
#define rep2(CNT, START, GOAL) for (int CNT = (int)(START); CNT < (int)(GOAL); CNT++)
#define rep3(CNT, START, GOAL) for (int CNT = (int)(START); CNT > (int)(GOAL); CNT--)
#define all(CONT) begin(CONT), end(CONT)
template <typename T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template <typename T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
void prec(const int &DIG) { cout << fixed << setprecision(DIG); cerr << fixed << setprecision(DIG); }
template <typename T> void CERR(const T &ELEM) { cerr << ELEM; }
#define dbl(OBJ) cerr << #OBJ << ": "; CERR(OBJ); cerr << "\n"
template <typename T, typename ...Ts> void CERR(const T &FIRST, const Ts &...REST) { CERR(FIRST); cerr << ", "; CERR(REST...); }
#define dbs(...) cerr << "(" << #__VA_ARGS__ << "): ("; CERR(__VA_ARGS__); cerr << ")\n"
#define itrep(ITR, CONT) for (auto ITR = begin(CONT); ITR != end(CONT); ITR++)
template <typename T> void CERR(const vector<T> &VEC) { cerr << "{ "; itrep(ITR, VEC) { CERR(*ITR); cerr << ", "; } cerr << "}"; }
#define YN(FLG) cout << (FLG ? "YES" : "NO") << "\n"
#define Yn(FLG) cout << (FLG ? "Yes" : "No") << "\n"
#define yn(FLG) cout << (FLG ? "yes" : "no") << "\n"

// #include <atcoder/all>

// using namespace atcoder;

// const ll INF = LONG_LONG_MAX;
const int INF = INT_MAX;
// const ll MOD = 1000000007; // 998244353;

// d = |B-A|とし，絶対値がC以上D以下の数をN-1個加えてdを作ることができるかを判定する
// +(or0)の数をk個，-の数をN-1-k個使うとすると(0<=k<=N-1)，
// 和の最大値は D*k-C*(N-1-k) , 最小値は C*k-D*(N-1-k) で，和はこれらの間の値を1刻みで全て取れる。

int main() {
	ll N, A, B, C, D; cin >> N >> A >> B >> C >> D;
	ll d = abs(B - A);
	rep(k, N) {
		if (C * k - D * (N - 1 - k) <= d and d <= D * k - C * (N - 1 - k)) {
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
}

Measured memory_bytes: 3672
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<queue>
#include<map>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef pair<int,int> P;

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

int f(int x){
    int res=0;
    while(x%2==0){
        x /= 2;
        res++;
    }
    return res;
}

int main(){
    ll n,m;
    cin >> n >> m;
    ll a[n];
    rep(i,n) cin >> a[i];

    rep(i,n) a[i] /= 2;

    int t = f(a[0]);
    rep(i,n){
        if(f(a[i]) != t){
            cout << 0 << endl;
            return 0;
        }
        a[i] >>= t;
    }
    m >>= t;

    ll l = 1;
    rep(i, n){
        l = lcm(l,a[i]);
        if(l>m){
            cout << 0 << endl;
            return 0;
        }
    }

    m /= l;
    int ans = (m+1)/2;
    cout << ans << endl;


}

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

#define REP(i, n) for(int i=0; i<n;i++)
#define REPR(i, n) for(int i=n-1 ; i>=0; i--)
#define FOR(i, m, n) for(int i=m; i<n; i++)

#define INF 2e9
#define ll long long

int main(){
    int a, p;
    cin>>a>>p;
    cout<<(a*3+p)/2<<endl;
    return 0;
}

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

using namespace std;
using llong = long long;
using ldbl = long double;
using P = pair<llong, llong>;

#define ALL(x) x.begin(), x.end()

const llong inf = 1100100100100100ll;
const llong mod = 1e9+7;

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

	int cnt = 0;
	for (auto x : s)
		cnt += x == 'o';

	if (cnt + 15-(int)s.size() >= 8)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;

	return 0;
}

Measured memory_bytes: 256
# dp
import sys
from collections import defaultdict

stdin = sys.stdin
 
ni = lambda:int(ns())
na = lambda:list(map(int,stdin.readline().split()))
ns = lambda:stdin.readline().rstrip()  # ignore trailing spaces

MOD = 10 ** 9 + 7
d = dict()

N = ni()
C = [ni() for _ in range(N)]
dp = [1] * N
d[C[0]] = 0

for i in range(1, N):
    c = C[i]
    dp[i] = dp[i-1]
    if c in d:
        if d[c] != i-1:
            dp[i] += dp[d[c]]
    d[c] = i
    dp[i] %= MOD

print(dp[N-1])



Measured memory_bytes: 36880
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <vector>
#include <numeric>
#include <string>
#include <bitset>
#include <queue>
#include <tuple>
#include <regex>
#include <cmath>
#include <map>
#include <cstring>


using namespace std;

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

	if (S == "Sunny") {
	cout << "Cloudy" << endl;
	}
	else if (S == "Cloudy"){
		cout << "Rainy" << endl; 
	}
		
	else {
		cout << "Sunny" << endl;
	}

	
}

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

using namespace std;
const int MAXN = 4e5 + 5;
#define ll long long
int n;
ll d[MAXN], f[MAXN][2];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%lld", d + i);
	f[1][1] = -1e18;
	for (int i = 2; i <= n; i ++) {
		f[i][1] = max(f[i - 2][1], f[i - 2][0]) + d[i];
		f[i][0] = f[i - 2][0] + d[i - 1];
		
		if (i & 1) f[i][1] = max(f[i][1], max(f[i - 3][1], f[i - 3][0]) + d[i]);
	} 
	printf("%lld\n", max(f[n][0], f[n][1]));
	return 0;
} 

Measured memory_bytes: 8532
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            var a = input[0];
            var b = input[1];
            var answer = a < 10 && b < 10 ? a * b : -1;
            Console.WriteLine(answer);
        }
    }
}


Measured memory_bytes: 13396
use proconio::input;

#[proconio::fastout]
fn main() {
    input! {
        N: i128,
        X: i128
    }
    println!("{}", search(N, X));
}

fn search(level: i128, remaining: i128) -> i128 {
    if remaining <= 0 { return 0 }
    return if remaining >= length(level) {
        patty(level)
    } else if remaining > length(level - 1) + 1 {
        patty(level - 1) + 1 + search(level - 1, remaining - 2 - length(level - 1))
    } else {
        search(level - 1, remaining - 1)
    };
}

fn patty(n: i128) -> i128 { return (2i128 << n) - 1; }

fn length(n: i128) -> i128 { return (4i128 << n) - 3; }

Measured memory_bytes: 2176
import math
A=[int(input()) for _ in range(5)]
# A=sum([math.ceil(float(input()) / 10) * 10 for _ in range(5)])
K=0
V=0
for z in A:
  j = math.ceil(float(z) / 10) * 10
  V += j
  if K <= j - z:
    K = j - z
print(V - K)


Measured memory_bytes: 2940
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <vector>

using namespace std;

#define rep(i, n) for (int64_t i = 0; i < (n); i++)
#define irep(i, n) for (int64_t i = 0; i <= (n); i++)
#define rrep(i, n) for (int64_t i = (n)-1; i >= 0; i--)
#define rirep(i, n) for (int64_t i = n; i >= 0; i--)

template <typename F>
void forComb(int n, int k, F f)
{
    int comb = (1 << k) - 1;
    while (comb < (1 << n))
    {
        f(comb);

        int x = comb & -comb;
        int y = comb + x;
        comb = ((comb & ~y) / x >> 1) | y;
    }
}

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

    vector<int> honest(n), unkind(n);

    rep(i, n)
    {
        int a;
        cin >> a;

        honest[i] = unkind[i] = 0;
        rep(j, a)
        {
            int x, y;
            cin >> x >> y;
            x--;

            if (y == 1)
            {
                honest[i] |= 1 << x;
            }
            else
            {
                unkind[i] |= 1 << x;
            }
        }
    }

    int result = 0;
    rep(i, n)
    {
        forComb(n, i + 1, [&](int comb) {
            bool b = true;
            rep(i, n)
            {
                if (((comb >> i) & 1) != 0)
                {

                    b = b && (comb & honest[i]) == honest[i] && (~comb & unkind[i]) == unkind[i];
                }
            }
            if (b)
            {

                result = i + 1;
            }
        });
    }
    cout << result << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,m,ans=0;//n-switch,m-lit
struct lit
{
	int num;
	int ask[17];
	int ode;//odevity
	int cnt=0;
};
int fun(int x[])
{
	int i;
	for(i=1;i<=n;i++)
		if(x[i]!=1)
		{
			x[i]=1;
			return 0;
		}
		else
			x[i]=0;
			return 0;
}
int main(){
	//输入 
	cin>>n>>m;
	int x[n+7];memset(x,0,sizeof(x));
	lit b[m+7];
	for(int i=1;i<=m;i++)
	{
		cin>>b[i].num;
		for(int j=1;j<=b[i].num;j++)
		{
			cin>>b[i].ask[j];
		}
	}
	for(int i=1;i<=m;i++)
		cin>>b[i].ode;
	//功能 
	for(int i=1;i<=pow(2,n);i++)//开关组合数 
	{
		fun(x);
		for(int j=1;j<=m;j++)//灯数 
		{
			b[j].cnt=0;
			for(int k=1;k<=b[j].num;k++)//每灯关联开关数 
			{
				if(x[b[j].ask[k]]==1)
				{
					b[j].cnt++;
					continue;
				}
			}
			if(b[j].cnt%2==b[j].ode)
			{
				if(j<m) continue;
				else 
				{
					ans++;
					break;
				}
			}
			else break;
		}
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O2")
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<unordered_map>
#include<set>
#include<cmath>
#include<climits>
#include<random>
#include <iomanip>
#include <bitset>
#include <iomanip>
using namespace std;
 
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define fast ios::sync_with_stdio(false); cin.tie(NULL);
 
/////////////////////////////////////////////
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
///////////////////////////////
#define int long long

const int mod = 1e9 + 7;

void solve(){
	
	int n;
	cin>>n;
	vector<pair<int,int>> a(n);
	for(int i = 0 ; i < n ; ++i){
		
		cin>>a[i].ff>>a[i].ss;
	}
	sort(a.begin(),a.end());
	
	int x[4];
	for(int i = 0 ; i < 4 ; ++i)
		x[i] = -1e15;
	int ans = 0;
	for(int i = 0 ; i < n ; ++i){
		
		int p = a[i].ff + a[i].ss + x[0];
		int q = a[i].ff - a[i].ss + x[1];
		int r = -a[i].ff + a[i].ss + x[2];
		int s = -a[i].ff - a[i].ss + x[3];

		x[0] = max(x[0] , -a[i].ff - a[i].ss);
		x[1] = max(x[1] , -a[i].ff + a[i].ss);
		x[2] = max(x[2] , a[i].ff - a[i].ss);
		x[3] = max(x[3] , a[i].ff + a[i].ss);

		ans = max({ans , p , q , r , s});
	}

	cout<<ans<<endl;
}

signed main(){
 
	fast;
	int t = 1;
	//cin>>t;
	while(t--)
		solve();
}

Measured memory_bytes: 6344
//#include "debug.h"
#include <string.h>
#include <limits.h>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 700
int g[MAXN][MAXN];
int vis[MAXN];
int n, m;

int input() {
	if (scanf("%d %d", &n, &m) < 0) return 0;
	memset(g, 0, sizeof(g));
	for (int i=0; i<m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		x--, y--;
		g[x][y] = g[y][x] = 1;
	}
	return 1;
}

void init() {
	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
			if (i!=j)
				g[i][j] = 1-g[i][j];
	memset(vis, 0, sizeof(vis));
}

int dfs(int v,int c, int *ct) {
	vis[v] = c;
	ct[c-1]++;
	int m = 0;
	for (int i=0; i<n; i++)
		if (g[v][i]) {
			if (vis[i]) {
				if (vis[i]==c) return 0;
				continue;
			}
			if (!dfs(i, 3-c, ct)) return 0;
		}
	return 1;
}

long solve() {
	int ct[MAXN][2];
	memset(ct, 0, sizeof(ct));
	int m = 0;
	for (int i=0; i<n; i++)
		if (!vis[i]) {
			if (!dfs(i, 1, ct[m++])) return -1;
		}
	int b[2][MAXN+1];
	memset(b, 0, sizeof(b));
	int cur=0, next=1;
	b[cur][0] = 1;
	for (int i=0; i<m; i++) {
		memset(b[next], 0, sizeof(b[next]));
		for (int j=0; j<=n; j++)
			if (b[cur][j]) {
				for (int k=0; k<2; k++)
					b[next][j+ct[i][k]] = 1;
			}
		swap(cur, next);
	}
	int ans = INT_MAX;
	for (int i=0; i<=n; i++) {
		if (b[cur][i]) {
			int j = n-i;
			int s = i*(i-1)/2 + j*(j-1)/2;
			ans = min(ans, s);
		}
	}
	return ans;
}

void output(long ans) {
	printf("%ld\n", ans);
}

void cleanup() {
}

int main() {
	while (input()) {
		init();
		output(solve());
		cleanup();
		//break;
	}
}





Measured memory_bytes: 2048
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix
 
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    s=input().replace("BC","X")
#    print(s)
    c=0
    d=0
    for i in s:
        if i=="A":
            c+=1
        elif i=="X":
            d+=c
        else:
            c=0
    print(d)
#    while "AX" in s:
#        s=s.replace("AX","XA")
#        print(s)
if __name__ == '__main__':
    main()

Measured memory_bytes: 5608
import java.util.Scanner;
public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    while(true){
      int H = sc.nextInt();
      int W = sc.nextInt();
      if(H == 0 && W == 0)
      break;
      for(int i = 0;i < H;i++){
        for(int j = 0;j < W;j++){
          System.out.print("#");
        }
        System.out.print("\n");
      }
      System.out.println("");
    }
}
}


Measured memory_bytes: 35232
#include <iostream>
using namespace std;
int main(void){
    while(true){
        int n;
        cin >>n;
        if(n==0)break;
        int m,e,j,X,Y;
        for(int i=0;i<n;i++){
            cin >>m>>e>>j;
            X=(m+e+j)/3;
            Y=(m+e)/2;
            if(m==100||e==100||j==100){
                cout <<"A"<<endl;
            }
            else if(Y>=90){
                cout <<"A"<<endl;
            }
            else if(X>=80){
                cout <<"A"<<endl;
            }
            else if(X>=70){
                cout <<"B"<<endl;
            }
            else if(X>=50&&(m>=80||e>=80)){
                cout <<"B"<<endl;
            }
            else{
                cout<<"C"<<endl;
            }
        }
    }
}



Measured memory_bytes: 3028
#include <bits/stdc++.h>
#define PREP(i, s, x) for(ll i = (s); i < (x); i++)
#define MREP(i, s, x) for(ll i = (s); i >= (x); i--)
#define REP(i, x) PREP(i, 0, x)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// variable -------------------------------------------

constexpr ll INF = (1ll << 59);
constexpr ll MOD = 1000000007ll;

// structure ------------------------------------------


// Unionfind 素集合データ構造
struct Unionfind {
    vector<ll> par;
    vector<ll> rank;

    Unionfind(ll n) : par(n), rank(n) {
        REP(i, n) { par[i] = i; }
    }

    ll root(ll v) {
        if(par[v] == v) return v;
        return par[v] = root(par[v]);
    }

    void unite(ll x, ll y) {
        x = root(x);
        y = root(y);
        if(x == y) return;

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

    bool is_same(ll x, ll y) { return root(x) == root(y); }
};


// function -------------------------------------------

// main -----------------------------------------------

int main() {
	ll n, m;
	cin >> n >> m;

	Unionfind uf(n);
	REP(i, m){
		ll a, b;
		cin >> a >> b;
		a --, b --;
		uf.unite(a, b);
	}

	vector<ll> oya(n, 0);
	REP(i, n){
		oya[uf.root(i)] ++;
	}
	ll ans = 0;
	REP(i, n){
		chmax(ans, oya[i]);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 7952
mod = 2019
l, r = map(int, input().split())

if r//mod - l//mod > 0:
  print(0)
else:
  l %= mod
  r %= mod
  ans = mod - 1
  for i in range(l+1, r+1):
    for j in range(l, i):
      ans = min(i*j%mod, ans)
  print(ans)

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

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

Measured memory_bytes: 384
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define brep(index,num) for(int index=num-1;index>=0;index--)
#define brep1(index,num) for(int index=num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int dpl[3001][3001],dpr[3001][3001];
int main(){
	int N,W;
	int value[3001],weight[3001];
	scan(N);scan(W);
	W--;
	rep(i,N){
		scan(weight[i]);scan(value[i]);
	}
	rep(i,N){
		rep(w,W+1){
			if(w>=weight[i]) dpl[i+1][w]=max(dpl[i][w-weight[i]]+value[i],dpl[i][w]);
			else dpl[i+1][w]=dpl[i][w];
		}
	}
	rep(i,N+1) rep(w,W) dpl[i][w+1]=max(dpl[i][w+1],dpl[i][w]);
	brep1(i,N){
		rep(w,W+1){
			if(w>=weight[i-1]) dpr[i-1][w]=max(dpr[i][w-weight[i-1]]+value[i-1],dpr[i][w]);
			else dpr[i-1][w]=dpr[i][w];
		}
	}
	rep(i,N+1) rep(w,W) dpr[i][w+1]=max(dpr[i][w+1],dpr[i][w]);
	int ans=0;
	rep(i,N){
		int imax=0;
		rep(wl,W+1){
			int wr=W-wl;
			imax=max(imax,dpl[i][wl]+dpr[i+1][wr]);
			//printf("i:%d wl:%d wr:%d dpl[i][wl]:%d dpr[i+1][wr]:%d sum:%d\n",i,wl,wr,dpl[i][wl],dpr[i+1][wr],dpl[i][wl]+dpr[i+1][wr]);
		}
		ans=max(ans,imax+value[i]);
	}
	prin(ans);
	return 0;
}


Measured memory_bytes: 70656
def int_warizan(a, b):
    d = a // b
    return d


def amari_warizan(a, d):
    r = a % b
    return r


def float_warizan(a, b):
    f = a / b
    return f


num = input()
a, b = map(int, num.split())

print(f'{int_warizan(a, b)} {amari_warizan(a, b)} {float_warizan(a, b):.6f}')



Measured memory_bytes: 5628
import java.util.Scanner;

public class Main {

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

		// 整数の入力
		int left = sc.nextInt() + sc.nextInt();
		int right = sc.nextInt() + sc.nextInt();

		if(left > right){
			System.out.println("Left");
		}else if(right > left){
			System.out.println("Right");
		}else{
			System.out.println("Balanced");
		}

		sc.close();
	}

}


Measured memory_bytes: 21972
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define db long double
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()

void dout() { cerr << '\n'; }

template <typename Head, typename... Tail>
void dout(Head H, Tail... T) {
    cerr << " " << H;
    dout(T...);
}

#ifdef LOCAL
    #define dbg(...) cerr << #__VA_ARGS__, dout(__VA_ARGS__)
#else
    #define dbg(...) ;
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair <int, int> pii;

const int N = 1e5 + 123;
int n;
pii seg[N];

int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif

    cin >> n;
    set <pii> L, R;
    for (int i = 1; i <= n; i++) {
        cin >> seg[i].fi >> seg[i].se;
        L.insert({seg[i].fi, i});
        R.insert({seg[i].se, i});
    }
    pii cur = *(--L.end());
    ll res1 = abs(cur.fi);
    for (int i = 1; i < n; i++) {
        int x = cur.fi;
        if (i & 1) {
            L.erase(cur);
            R.erase({seg[cur.se].se, cur.se});
            cur = *R.begin();
            if (cur.fi >= x) {
                cur.fi = x;
                break;
            }
            res1 += x - cur.fi;
        }   else {
            R.erase(cur);
            L.erase({seg[cur.se].fi, cur.se});
            cur = *(--L.end());
            if (cur.fi <= x) {
                cur.fi = x;
                break;
            }
            res1 += cur.fi - x;
        }
    }
    res1 += abs(cur.fi);

    L.clear();
    R.clear();
    for (int i = 1; i <= n; i++) {
        L.insert({seg[i].fi, i});
        R.insert({seg[i].se, i});
    }

    cur = *R.begin();
    ll res2 = abs(cur.fi);
    for (int i = 1; i < n; i++) {
        int x = cur.fi;
        if (i % 2 == 0) {
            L.erase(cur);
            R.erase({seg[cur.se].se, cur.se});
            cur = *R.begin();
            if (cur.fi >= x) {
                cur.fi = x;
                break;
            }
            res2 += x - cur.fi;
        }   else {
            R.erase(cur);
            L.erase({seg[cur.se].fi, cur.se});
            cur = *(--L.end());
            if (cur.fi <= x) {
                cur.fi = x;
                break;
            }
            res2 += cur.fi - x;
        }
    }
    res2 += abs(cur.fi);
    cout << max(res1, res2);
}


Measured memory_bytes: 10368
#include <stdio.h>
#include <inttypes.h>

int32_t N;
int64_t A, B;
int64_t h[114514];

int main(void) {
	int32_t i;
	int64_t A_damage;
	int32_t ng, ok;
	int64_t hmax = 0;
	if (scanf("%" SCNd32 "%" SCNd64 "%" SCNd64, &N, &A, &B) != 3) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%" SCNd64, &h[i]) != 1) return 1;
		if (h[i] > hmax) hmax = h[i];
	}
	A_damage = A - B;
	ng = 0;
	ok = hmax;
	while (ng + 1 < ok) {
		int32_t mid = ng + (ok - ng) / 2;
		int64_t B_damage = B * mid;
		int32_t left = mid;
		for (i = 0; left >= 0 && i < N; i++) {
			int64_t this_left = h[i] - B_damage;
			if (this_left > 0) left -= (this_left + A_damage - 1) / A_damage;
		}
		if (left >= 0 && i >= N) ok = mid; else ng = mid;
	}
	printf("%" PRId32 "\n", ok);
	return 0;
}


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	uint64_t x; cin>>x;
	uint64_t a=100,ans=0;
	while(a<x)a*=1.01,++ans;
	cout<<ans<<"\n"s;
}

Measured memory_bytes: 3636
extern crate core;

use std::io::{self, Read};

#[macro_use]
mod parser {
    macro_rules! input {
    ($s:expr=>$($t:tt)*) => {
        let mut lines=$s.split("\n");
        $(
            line_parse!(lines,$t);
        )*
    };
    }

    macro_rules! line_parse {
    ($lines:expr,($($name:ident:$t:tt)*)) => {
        let mut line=$lines.next().unwrap().split_whitespace();
        $(value_def!(line,$name,$t);)*
    };

    //複数行
    ($lines:expr,{$n:expr;$name:ident:$t:tt}) => {
        values_def!($lines,$n,$name,$t);
    };
    }

    macro_rules! value_def {
    ($line:expr,$name:ident,$t:tt) => {
        let $name=value!($line,$t);
    };
    }

    macro_rules! values_def {
    ($lines:expr,$n:expr,$name:ident,$t:tt) => {
        let $name={
        let mut vec=Vec::new();
        for i in 0..$n{
            let mut next=$lines.next().unwrap().split_whitespace();
            vec.push(value!(next,$t));
        }
        vec
        };
    };
    }

    macro_rules! value {
    //配列
    ($line:expr,[$t:tt]) => {
        $line.map(|x|{
        let mut iter=::std::iter::once(x);
        value!(iter,$t)
        }).collect::<Vec<_>>()
    };
    //タプル
    ($line:expr,($($t:tt),*)) => {
        ($(value!($line,$t),)*)
    };
    //文字列
    ($line:expr,#) => {
        $line.next().unwrap()
    };
    //単一値
    ($line:expr,$t:ty) => {
        $line.next().unwrap().parse::<$t>().unwrap()
    };
    }
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).unwrap();
    let output = run(input.trim().to_string());
    println!("{}", output);
}

fn run(input: String) -> String {
    input!(input=>
        (n:usize)
        (c:[i64])
        (q:usize)
        {q;list:(i64,usize,i64)});
    let mut apb = Vec::new();
    for _ in 0..n {
        apb.push(0);
    }

    for (t, x, d) in list {
        if t == 1 {
            //収穫
            apb[x - 1] += d;
            if apb[x - 1] > c[x - 1] {
                return x.to_string();
            }
        } else {
            //出荷
            apb[x - 1] -= d;
            if apb[x - 1] < 0 {
                return x.to_string();
            }
        }
    }

    0.to_string()
}

macro_rules! tests {
    ($($name:ident: $input:expr=>$output:expr,)*) => {
        mod tests {
            $(
                #[test]
                fn $name() {
                    assert_eq!(super::run($input.to_string()), $output.to_string());
                }
            )*
        }
    }
}

tests! {
    test1: "2
3 3
4
1 1 2
1 2 3
2 1 3
2 2 3" => "1",
    test2: "2
3 3
4
1 1 3
2 1 2
1 2 3
1 1 3" => "1",
    test3: "3
3 4 5
4
1 1 3
1 2 3
1 3 5
2 2 2" => "0",
    test4: "6
28 56 99 3 125 37
10
1 1 10
1 1 14
1 3 90
1 5 10
2 3 38
2 1 5
1 3 92
1 6 18
2 5 9
2 1 4" => "3",
}



Measured memory_bytes: 13840
#include <bits/stdc++.h>
using namespace std;
using ll = int_fast64_t;
using ld = long double;
#define dump(x) cout << #x << " = " << x << "\n";
#define SELECTOR(_1, _2, _3, SELECT, ...) SELECT
#define rep(...) SELECTOR(__VA_ARGS__, _rep1, _rep0)(__VA_ARGS__)
#define _rep0(i, n) for (ll i = 0; i < n; ++i)
#define _rep1(i, k, n) for (ll i = k; i < n; ++i)
template <typename T> void vecout(const T &v) {
  for(auto it=v.begin();it!=v.end();++it,cout<<(it!=v.end()?" ":"\n")) {
    cout << *it;
  }
}

ld dp[303][303][303]={};

void solve(){
  // main coding
  ll n; cin>>n;
  vector<ll> cnt(3);
  rep(_,n) {
    ll a; cin>>a;
    --a;
    cnt[a]++;
  }
  function<ld(ll,ll,ll)> calc=[&](ll i,ll j,ll k){
    if(dp[i][j][k]) return dp[i][j][k];
    ld l=i+j+k;
    if(l==0) return (ld)0;
    return dp[i][j][k]=(i?calc(i-1,j,k)*i/l:0)+(j?calc(i+1,j-1,k)*j/l:0)+(k?calc(i,j+1,k-1)*k/l:0)+n/l;
  };
  cout<<calc(cnt[0],cnt[1],cnt[2])<<"\n";
}

int main(){
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(10);
  solve();
  return 0;
}


Measured memory_bytes: 432512
#include <stdio.h>

int main(){
    int N;
    scanf("%d", &N);
    int mx = 0, mn = 1000;
    for(int i=0; i<N; i++){
        int x;
        scanf("%d", &x);
        if(x > mx) mx = x;
        if(x < mn) mn = x;
    }
    printf("%d", mx-mn);
    return 0;
}

Measured memory_bytes: 128
<?PHP
$first_line = fgets(STDIN);
$second_line = fgets(STDIN);
$first_line_array = explode(" ", $first_line);
$steps_amount=$first_line_array[0];
//ジャンプで飛べる足場の数
$skip_power=$first_line_array[1];
$steps_heights = explode(" ", $second_line);

$dps=[];

foreach (range(0, $steps_amount-1) as $index) {
    $dps[$index] = INF;
    if($index===0){
        $dps[0]=0;
        continue;
    }
    $dps[$index]=$dps[$index-1]+abs($steps_heights[$index]-$steps_heights[$index-1]);

    foreach (range(1, $skip_power) as $i) {
        if($index>=$i){
            if ($dps[$index]> abs($dps[$index - $i] + abs($steps_heights[$index] - $steps_heights[$index - $i]))){$dps[$index]=abs($dps[$index - $i] + abs($steps_heights[$index] - $steps_heights[$index - $i]));}
        }

    }
}

echo end($dps);

Measured memory_bytes: 23028
#include<cstdio>
#include<cstdlib>
#include<cstring>

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

Node *nil;

Node* listSearch(int key);
void init();
void printList();
void deleteNode(Node *t);
void deleteFirst();
void deleteLast();
void deleteKey(int key);
void insert(int key);

int main() {
  int key, n, i;
  char com[20];
  scanf("%d", &n);
  init();
  for ( i = 0; i < n; i++ ) {
    scanf("%s%d", com, &key);
    if ( com[0] == 'i' ) insert(key);
    else if ( strlen(com) == 6 ) deleteKey(key);
    else if ( com[6] == 'F' ) deleteFirst();
    else deleteLast();
  }

  printList();

  return 0;
}

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

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

void printList() {
  Node *cur = nil->next;
  int isf = 0;
  while ( 1 ) {
    if ( cur == nil ) break;
    if ( isf++ > 0 ) printf(" ");
    printf("%d", cur->key);
    cur = cur->next;
  }
  printf("\n");
}

void deleteNode(Node *t) {
  if ( t == nil ) return;
  t->prev->next = t->next;
  t->next->prev = t->prev;
  free(t);
}

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

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

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

void insert(int key) {
  Node *x = (Node *)malloc(sizeof(Node));
  x->key = key;
  x->next = nil->next;
  nil->next->prev = x;
  nil->next = x;
  x->prev = nil;
}


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

int way;
long long int cost[102];

bitset<102> dv[102];
long long int C;

vector<int> gr[102];

bool pos[102];


inline void dfs(long long int idx, bitset<102> val) {
	if (idx == 27) {
		long long int ans = 0;
		for (int j = 1; j <= 26; j++) {
			if ((val&dv[j]) == 0LL) {
				ans += cost[j];
			}
		}
		for (int j = 27; j <= 50; j++) {
			if (j * 3 <= 100 && j % 2) {
				if ((dv[j] & val).any())continue;
				long long int U = cost[j];
				if ((val&dv[j * 2]) == 0LL) {
					U += max(0LL, cost[j * 2]);
				}
				if ((val&dv[j * 3]) == 0LL) {
					U += max(0LL, cost[j * 3]);
				}
				if (U >= 0) {
					ans += cost[j];
				}
				else {
					val.set(j, 1);
					//val |= (1LL << (long long int)(j));
				}
				continue;
			}
			if (j * 3 <= 100) {
				int o1 = j;
				int o2 = j * 3 / 2;
				long long int www = 0;
				int id = -1;
				for (int k = 0; k < 4; k++) {
					auto val2 = val;
					if (k & 1) {
						val2.set(o1, 1);
						//val2 |= (1LL << (long long int)(o1));
					}
					if ((k >> 1) & 1) {
						//val2 |= (1LL << (long long int)(o2));
						val2.set(o2, 1);
					}
					long long int ad = 0;
					for (auto el : gr[j]) {
						if ((dv[el] & val2) == 0LL) {
							if (el >= 50) {
								ad += max(0LL, cost[el]);
							}
							else {
								ad += cost[el];
							}
						}
					}
					www = max(www, ad);
					if (www == ad) {
						id = k;
					}
				}
				if (id & 1) {
					val.set(o1, 1);
					//val |= (1LL << (long long int)(o1));
				}
				if ((id >> 1) & 1) {
					//val |= (1LL << (long long int)(o2));
					val.set(o2, 1);
				}
				for (auto el : gr[j]) {
					if ((dv[el] & val) == 0LL) {
						if (el >= 50) {

						}
						else {
							ans += cost[el];
						}
					}
				}
				continue;
			}
			if (pos[j] == false) {
				if ((val&dv[j]).any())continue;
				long long int nex = j * 2;
				long long int U = cost[j];
				if ((val&dv[nex]) == 0LL) {
					U += max(0LL, cost[nex]);
				}
				if (U >= 0) {
					ans += cost[j];
				}
				else {
					val |= (1LL << (long long int)(j));
				}
				continue;
			}
		}
		for (int j = 51; j <= 100; j++) {
			if ((val&dv[j]).any()) {
				continue;
			}
			ans += max(0LL, cost[j]);
		}
		C = max(C, ans);

		return;
	}
	bool ng = false;
	if ((val&dv[idx]).any()) {
		ng = true;
	}
	if (ng == false) {
		dfs(idx + 1, val);
	}
	val.set(idx, 1);
	dfs(idx + 1, val );
}

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= 100; i++) {
		scanf("%lld", &cost[i]);
	}
	for (int i = 1; i <= 100; i++) {
		for (int j = 1; j <= i; j++) {
			if (i%j == 0) {
				dv[i].set(j, 1);// |= (1LL << (long long int)(j));
			}
		}
		if (i >= 27) {
			if (i * 3 <= 100) {
				gr[i].push_back(i);
				gr[i].push_back(i * 3);
				gr[i].push_back(i * 3 / 2);
				gr[i].push_back(i * 2);
				if ((i * 3) % 2 == 0)pos[i * 3 / 2] = true;
			}
		}
	}
	dfs(1, 0);
	printf("%lld\n", C);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N - 1; i >= 0; i--)
const ll INF = 1000000000;
//const ll MOD = 1000000007;
const ld PI = (acos(-1));
using Graph = vector<vector<int>>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true;} return false;}
typedef pair<int, int> P;
double rad(double a) {return a * 180 / PI;}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

//dpTable
int dp[100050];

int main(){
    int N,M;
    cin >> N >> M;
    cout << (1900 * M + 100 * (N - M)) * pow(2,M) << endl;
    return 0;
}

Measured memory_bytes: 4200
#include<iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int sum = 0;
    int ans = 1e9;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        sum += a;
        if(ans > sum/(i+1))ans = sum/(i+1);
    }
    cout << ans << endl;
}



Measured memory_bytes: 3104
S = input()
dp = [[0]*13 for _ in range(len(S))]
if S[0]=="?":
  dp[0] = [1]*10+[0]*3
else:
  dp[0][int(S[0])] = 1
mod = 10**9+7
table = {str(i):[(10*j+i)%13 for j in range(13)] for i in range(10)}
for k in range(1,len(S)):
  tmp = dp[k-1]
  if S[k] != "?":
    for i,t in enumerate(table[S[k]]):
      dp[k][t]= tmp[i]
  else:
    for j in range(10):
      for i,t in enumerate(table[str(j)]):
        dp[k][t] += tmp[i]%mod
    dp[k] = [p%mod for p in dp[k]]
print(dp[-1][5])
    
    


Measured memory_bytes: 79836
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include <numeric>
using namespace std;
typedef unsigned long long int ulint;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define RE return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=(int)1000000007;
const llint big=(llint)(2.19e15)+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else{return gcd(b,a%b);}}
llint lcm(llint a,llint b){return a/gcd(a,b) *b;}
template<class T,class U> auto LB(T& ve,U in){return lower_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto UB(T& ve,U in){return upper_bound(ve.begin(),ve.end(),in);}
template<class T,class U> auto LBI(T& ve,U in){return LB(ve,in)-ve.begin();}
template<class T,class U> auto UBI(T& ve,U in){return UB(ve,in)-ve.begin();}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
using pli=pair<llint,int>;
using daic=priority_queue<pli,vector<pli>,greater<pli>>;
int main(void){
	//d固定かい!!!
	int h,w,D,i,j,k;cin>>h>>w>>D;
	vector<int>ta(h*w+1);
	vector<int>yo(h*w+1);
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			int a;cin>>a;a--;
			ta[a]=i;
			yo[a]=j;
		}
	}
	vector<int>twa(h*w+1);
	vector<int>ywa(h*w+1);
	for(i=D;i<=h*w;i++){
		twa[i]=abs(ta[i]-ta[i-D])+twa[i-D];
		ywa[i]=abs(yo[i]-yo[i-D])+ywa[i-D];
	}
	int q;cin>>q;
	while(q--){
		int l,r;cin>>l>>r;
		l--;r--;
		cout<<twa[r]+ywa[r]-twa[l]-ywa[l]<<endl;
	}
	RE;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define For(i,x,y) for (register int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (register int i=(x);i<(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define Debug(v) for (auto i:v) printf("%lld ",i);puts("")
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fil(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef pair<ll,ll> PA;
typedef vector<int> poly;
inline ll read(){
    ll x=0,f=1;char c=getchar();
    while ((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if (c=='-') f=-1,c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

const int N = 110;
int n,k;
ll ans;
char s[N];

int main(){
	scanf("%s%d",s+1,&k),n=strlen(s+1);
	bool flag=1;
	For(i,2,n) flag&=s[i]==s[1];
	if (flag) return printf("%lld\n",1ll*n*k/2),0;
	int x=0,y=0;
	for (int l=1,r=1;l<=n;l=++r){
		while (r<n&&s[r+1]==s[l]) ++r;
		if (l==1) x=r-l+1;
		if (r==n) y=r-l+1;
		ans+=1ll*((r-l+1)/2)*k;
	}
	if (s[1]==s[n]&&(x&1)&&(y&1)) ans+=k-1;
	printf("%lld\n",ans);
}

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

int main(){
    int a, b, cnt;
    cin >> a;
    vector<int> arr(a);
    b = 1000;
    cnt = 1;
    int tmp = 0;
    for (int i = 0; i < a; i++) cin >> arr.at(i); 
    for (int j = 0; j < arr.size(); j++){
        if (arr[j] != cnt) {
            tmp++;
        }
        cnt++;
    }
    if (tmp <= 2) cout << "YES" << endl;
    else cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <complex>
#include <cassert>

#define enp     puts("**chkchkchkchkchk**")
#define A       first
#define B       second
#define MP      make_pair

using namespace std;

typedef long long ll;
typedef unsigned int uint;

const int INF = 0x60000000;
const int MINF = -1000000000;
const int mod = 99999997;
const ll cons = 100000000000;
const double pi = 3.141592653589793;



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

	string correct = "CODEFESTIVAL2016";

	int ans = 0;

	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] != correct[i])ans++;
	}

	printf("%d\n", ans);


	return 0;
}

Measured memory_bytes: 384
import itertools
N=[int(x) for x in input()]
op=['+','-']
for op1 in op:
  for op2 in op:
    for op3 in op:
      if op1=='+': ans=N[0]+N[1]
      else: ans=N[0]-N[1]
      if op2=='+': ans+=N[2]
      else: ans-=N[2]
      if op3=='+': ans+=N[3]
      else: ans-=N[3]
      if ans==7:
        print(N[0],end="")
        print(op1,end="")
        print(N[1],end="")
        print(op2,end="")
        print(N[2],end="")
        print(op3,end="")
        print(N[3],end="")
        print("=7")
        exit()

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 0;
    for(int i = 0; i < n-2; i++) {
        if(s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C') {
            ans++;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
A = [int(x) for x in input().split()]

num_negative = sum([1 for x in A if x < 0])
absA = [abs(x) for x in A]
if num_negative % 2 == 0:
    print(sum(absA))
else:
    print(sum(absA)-min(absA)*2)


Measured memory_bytes: 65568
#include<stdio.h>
int main(void) {
	int a[4], b[4];
	int i;
	for (i = 0; i < 4; i++) {
		scanf("%d %d", &a[i], &b[i]);
		if (a[i] == 1) printf("%d\n", 6000*b[i]);
		else if (a[i] == 2) printf("%d\n", 4000*b[i]);
		else if (a[i] == 3) printf("%d\n", 3000*b[i]);
		else printf("%d\n", 2000*b[i]);
	}
	
	return 0;
}

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

int main(void) {

  string s;
  cin >> s;

  ll ans = 0;

  int n = s.size() - 1;

  for (int bit = 0; bit < (1 << n); bit++) {
    vector<bool> pin(11, false);
    for (int i = 0; i < n; i++) {
      if (bit & (1 << i)) {
        pin[i] = true;
      }
    }

    string tmp = "";
    for (int i = 0; i < n + 1; i++) {
      tmp = tmp + s[i];
      if (pin[i]) {
        ans += stoi(tmp);
        tmp = "";
      }
      if (i == n) ans += stoll(tmp);
    }
    
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void) {
	long long int q, h, s, d, n;
	scanf("%lld %lld %lld %lld", &q, &h, &s, &d);
	scanf("%lld", &n);
	long long int cost = 0, count = 0;
	if (q * 8 < h * 4 && q * 8 < s * 2 && q * 8 < d) {
		count = n / 0.25;
		n -= 0.25 * count;
		cost += q * count;
		printf("%lld", cost);
		return 0;
	} else if (h * 4 < q * 8 && h * 4 < s * 2 && h * 4 < d) {
		count = n / 0.5;
		n -= 0.5 * count;
		cost += h * count;
		if (n == 0) {
			printf("%lld", cost);
			return 0;
		}
		count = n / 0.25;
		n -= 0.25 * count;
		cost += q * count;
		printf("%lld", cost);
		return 0;
	} else if (s * 2 < h * 4 && s * 2 < q * 8 && s * 2 < d) {
		count = n / 1;
		n -= 1 * count;
		cost += s * count;
			if (n == 0) {
			printf("%lld", cost);
			return 0;
		}
		if (q * 8 < h * 4 && q * 8 < d) {
			count = n / 0.25;
			n -= 0.25 * count;
			cost += q * count;
			printf("%lld", cost);
			return 0;
		} else if (h * 4 < q * 8 && h * 4 < d) {
			count = n / 0.5;
			n -= 0.5 * count;
			cost += h * count;
			if (n == 0) {
				printf("%lld", cost);
				return 0;
			}
			count = n / 0.25;
			n -= 0.25 * count;
			cost += q * count;
			printf("%lld", cost);
			return 0;
		}
	} else if (d < h * 4 && d < s * 2 && d < q * 8) {
		count = n / 2;
		n -= 2 * count;
		cost += d * count;
			if (n == 0) {
			printf("%lld", cost);
			return 0;
		}
		if (q * 8 < h * 4 && q * 8 < s * 2) {
			count = n / 0.25;
			n -= 0.25 * count;
			cost += q * count;
			printf("%lld", cost);
			return 0;
		} else if (h * 4 < q * 8 && h * 4 < s * 2) {
			count = n / 0.5;
			n -= 0.5 * count;
			cost += h * count;
			if (n == 0) {
				printf("%lld", cost);
				return 0;
			}
			count = n / 0.25;
			n -= 0.25 * count;
			cost += q * count;
			printf("%lld", cost);
			return 0;
		}else if (s * 2 < h * 4 && s * 2 < q * 8) {
			count = n / 1;
			n -= 1 * count;
			cost += s * count;
				if (n == 0) {
				printf("%lld", cost);
				return 0;
			}
			if (q * 8 < h * 4) {
				count = n / 0.25;
				n -= 0.25 * count;
				cost += q * count;
				printf("%lld", cost);
				return 0;
			} else if (h * 4 < q * 8) {
				count = n / 0.5;
				n -= 0.5 * count;
				cost += h * count;
				if (n == 0) {
					printf("%lld", cost);
					return 0;
				}
				count = n / 0.25;
				n -= 0.25 * count;
				cost += q * count;
				printf("%lld", cost);
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 128
//(・ω・)
#include <stdio.h>
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, atoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip> //setprecision
#include <limits>
#include <sstream> //istringstream
#include <stdlib.h>
#include <list>
#include <iterator>//std::advance()
using namespace std;

int main(){
   int n;
   cin >> n;
   vector<string> s(n);
   int ac=0,wa=0,tle=0,re=0;
   for(int i=0; i<n; i++){
      cin >> s[i];
      if(s[i].size()==3) tle++;
      else if(s[i]=="AC") ac++;
      else if(s[i]=="WA") wa++;
      else re++;
   }
   cout << "AC x " << ac << endl;
   cout << "WA x " << wa << endl;
   cout << "TLE x " << tle << endl;
   cout << "RE x " << re << endl;
}



Measured memory_bytes: 6428