akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

/*
struct State
{
    int x, y, d;
};

bool operator<(const State &l, const State &r)
{
    return l.d > r.d;
}
*/

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

    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
    }
    int st, gt;
    cin >> st >> gt;
    st--;
    gt--;
    // dist[i][j] := 頂点i, mod3 = j に到達する最短距離
    vector<vector<int>> dist(n, vector<int>(3, INF));
    queue<P> que;
    que.push(P(st, 0));
    dist[st][0] = 0;
    while (!que.empty())
    {
        P p = que.front();
        que.pop();
        int cur = p.first, m = p.second;
        int nm = (m + 1) % 3;
        for (auto v : g[cur])
        {
            if (dist[v][nm] != INF)
                continue;
            dist[v][nm] = dist[cur][m] + 1;
            que.push(P(v, nm));
        }
    }
    cout << (dist[gt][0] != INF ? dist[gt][0] / 3 : -1) << endl;
}


Measured memory_bytes: 11264
# -*- coding: utf-8 -*-
n = int(input())
a = [int(i) for i in input().split()]

ans = 0
for i in range(n):
    #print(i, a[i], a[a[i] - 1])
    if a[a[i] - 1] == i + 1:
        ans += 1
print(ans // 2)


Measured memory_bytes: 13880
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        String[] strings = line.split(" ");
        
        String op = strings[1];
        int X = Integer.parseInt(strings[0]);
        int Y = Integer.parseInt(strings[2]);
        
        int answer;
        if (op.equals("+")) {
            answer = X + Y;
        } else {
            answer = X - Y;
        }
        
        System.out.println(answer);
        
    }
}


Measured memory_bytes: 23124
import java.util.*;
import java.io.*;

public class Main {
	private static void solve(){
		//Implement solution here.
		int k = ni();
		int x = ni();
		int s = x - k + 1;
		int e = x + k - 1;
		for(int i = s; i <= e; i ++) {
			System.out.print(i + " ");
		}
	}

	//Switch input source (stdin/file)
	private static BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args){
		String debugDataPath = System.getenv("DD_PATH");        
		if(debugDataPath != null){
			try{
				br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
			}catch(Exception e){
				throw new RuntimeException(e);
			}
		} 
		solve();
	}

	//Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
	//Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
	//Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
	//Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
	//Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
	//Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}

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

using namespace std;
typedef long long int ll;

const ll p = 31;
const ll N = 1e9 +1;


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

 
  ll n;
  cin>>n;
  ll ans = n*n*n;
  cout<<ans;


}

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

AC = []
count1 = 0
for i in range(N):
  
  if(i != 0):
   if((S[i-1] == 'A')and(S[i] == 'C')):
    count1 += 1
  AC.append(count1)

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


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

using namespace std;

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

const long long INF = 1LL << 60;

string s, t;
int dp[3100][3100];

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

  for (int i = 0; i < s.size(); i++) {
    for (int j = 0; j < t.size(); j++) {
      if (s[i] == t[j]) chmax(dp[i + 1][j + 1], dp[i][j] + 1);
      chmax(dp[i + 1][j + 1], dp[i + 1][j]);
      chmax(dp[i + 1][j + 1], dp[i][j + 1]);
    }
  }

  string res = "";
  int i = (int)s.size(), j = (int)t.size();

  while (i > 0 && j > 0) {
    if (dp[i][j] == dp[i - 1][j])
      i--;
    else if (dp[i][j] == dp[i][j - 1])
      j--;
    else {
      res = s[i - 1] + res;
      i--, j--;
    }
  }

  cout << res << endl;

  return 0;
}

Measured memory_bytes: 37120
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ull unsigned long long


using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);	
    cin.tie(NULL);
    
    int a, b, c, d; cin >> a >> b >> c >> d;
    
    while(a >= 0 && c >= 0)
    {
		c -= b;
		if(c <= 0) break;
		a -= d;
	}
	
	cout << (a > 0 ? "Yes" : "No") << endl;
    
    return 0;
}



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

bool isPrime(int n){

	if(n<=1)
		return false;
	if(n==2)
		return true;
	if(n%2==0)
		return false;
	for(int i=3; i*i<=n; i=i+2){
		if(n%i==0)
			return false;
	}

	return true;
}	

int main(){
	int n,cnt=0;
	cin >> n;
	int A[n];
	for(int i=0; i<n; i++)
		cin >>A[i];
	
	for(int i=0; i<n; i++){
		if(isPrime(A[i]))
			cnt++;
	}
	
	cout <<cnt<<endl;
}

Measured memory_bytes: 1196
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main { 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String line = sc.nextLine();
		int baseNumber = Integer.parseInt(line);
		System.out.println(baseNumber*baseNumber);
		
		
	}
}

Measured memory_bytes: 23508
/*input
30
*/
fn read_line() -> String {
    let mut return_ = format!("");
    std::io::stdin().read_line(&mut return_).ok();
    return_.trim().to_string()
}

fn main() {
    let v: u32 = read_line().parse().unwrap();
    for i in 1..v + 1 {
        if i % 3 == 0
            || match i.to_string().find('3') {
                Some(_) => true,
                None => false,
            }
        {
            print!(" {}", i);
        }
    }
    print!("\n");
}



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

using namespace std;

typedef long long llint;
typedef pair <int, int> pi;

const int MAXN = 100005;

int R, C, n, cnt;
int x[MAXN], y[MAXN], cost[MAXN], bio[MAXN], val[MAXN], mx[MAXN], mn[MAXN];
vector <pi> r[MAXN], v[MAXN];

void dfs (int x, int curr) {
    if (bio[x]) return;
    bio[x] = cnt;
    val[x] = curr;
    mn[cnt] = min(mn[cnt], val[x]);
    for (auto par : v[x]) {
        int sus = par.first, dif = par.second;
        dfs(sus, curr + dif);
    }
}

bool check () {
    for (int i = 1; i <= C; i++) {
        for (auto par : v[i]) {
            int sus = par.first, dif = par.second;
            if (val[sus] - val[i] != dif) return 0;
        }
    }
    for (int i = 1; i <= cnt; i++) {
        if (mx[i] > mn[i]) return 0;
    }
    return 1;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> R >> C >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> cost[i];
        r[x[i]].push_back({y[i], cost[i]});
    }
    for (int i = 1; i <= R; i++) {
        sort(r[i].begin(), r[i].end());
        for (int j = 1; j < r[i].size(); j++) {
            int dif = r[i][j].second - r[i][j - 1].second;
            v[r[i][j - 1].first].push_back({r[i][j].first, dif});
            v[r[i][j].first].push_back({r[i][j - 1].first, -dif});
        }
    }
    for (int i = 0; i < n; i++) {
        if (bio[y[i]] == 0) {
            cnt++;
            mn[cnt] = 1e9;
            dfs(y[i], cost[i]);
        } else {
            mx[bio[y[i]]] = max(mx[bio[y[i]]], val[y[i]] - cost[i]);
        }
    }
    if (check()) cout << "Yes"; else cout << "No";
    return 0;
}


Measured memory_bytes: 14900
def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
from math import log2,ceil

n,k=n1()

ans=0
for i in range(1,min(n,k)+1):
    a=k/i
    b=0.5**ceil(log2(a))
    ans+=b

if k<n:    
    ans+=(n-k)
print(ans/n)

Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>
using namespace std;

vector<pair<int, long long> > v[2509];
vector<int> rv[2509];
queue<int> q;
bool iq[2509], pr[2509];
int c[2509];
long long d[2509];

void dfs(int n)
{
	pr[n] = true;
	for (int i = 0; i < rv[n].size(); i++) {
		int tn = rv[n][i];
		if (!pr[tn])
			dfs(tn);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, p; cin >> n >> m >> p;
	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;
		v[a].push_back(make_pair(b, p - c));
		rv[b].push_back(a);
	}
	dfs(n);
	if (!pr[1]) {
		cout << -1 << '\n';
		return 0;
	}
	for (int i = 1; i <= n; i++)
		d[i] = 1000000000000000LL;
	d[1] = 0;
	q.push(1); iq[1] = true; c[1]++;
	while (!q.empty()) {
		int hn = q.front(); q.pop();
		iq[hn] = false;
		for (int i = 0; i < v[hn].size(); i++) {
			int tn = v[hn][i].first;
			if (pr[tn] && d[hn] + v[hn][i].second < d[tn]) {
				d[tn] = d[hn] + v[hn][i].second;
				if (!iq[tn]) {
					c[tn]++; iq[tn] = true;
					if (c[tn] >= n) {
						cout << -1 << '\n';
						return 0;
					}
					q.push(tn);
				}
			}
		}
	}
	cout << max(0LL, d[n] * -1) << '\n';
	return 0;
}	

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()




int main(){
    int n,m,x,y;
    cin>>n>>m>>x>>y;
    vector<int> p(n), q(m);
    rep(i,n) cin>>p[i];
    rep(i,m) cin>>q[i];
    p.push_back(x); q.push_back(y);
    sort(etob(p)); sort(btoe(q));
    int a=p[0], b=q[0];
    if(a<b) cout<<"No War"<<endl;
    else cout<<"War"<<endl;
}

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

#define ll long long
#define ld long double
 
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
 
#define err() cout<<"=================================="<<endl;
#define errA(A) for(auto i:A)   cout<<i<<" ";cout<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl

#define pb push_back
#define all(A)  A.begin(),A.end()
#define allr(A)    A.rbegin(),A.rend()
#define ft first
#define sd second
 
#define pll pair<ll,ll>
#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>
 
#define endl "\n"
 
const ll logN = 20;
const ll M = 1000000007;
const ll INF = 1e12;
#define PI 3.14159265
 
const ll N = 100005;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll k;
    string s;
    cin>>k>>s;
    ll n = s.length();
    if(n <= k){
        cout << s << endl;
    }
    else{
        string res;
        rep(i,0,k)  res += s[i];
        res += "...";
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 3668
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict


N = int(read().rstrip())

counter = defaultdict(int)  # 関数でdefault値を設定する

for x in range(1, N+1):
    first = str(x)[0]
    last = str(x)[-1]
    counter[(first, last)] += 1

ans = 0
items = list(counter.items())  # ループ内で存在しない可能性のある値にアクセスするので、list化する 
for (first, last), cnt in items:
    ans += cnt * counter[(last, first)]

print(ans)

Measured memory_bytes: 3316
N = gets.to_i
as = gets.split.map(&:to_i)

num = 0
N.times do |i|
    if as[i] < 0
        num += 1
        as[i] *= -1
    end
end
as.sort!
as[0] *= -1 if num % 2 == 1
puts as.inject(:+)

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


int main(){
    long long N;
    cin >> N;
    vector<long long> vec(N);
    long long n = 0;
    long long ans = 0;
    long long m = 0;
    long long mx = 0;
    
    for(int i = 0;i<N;i++){
        cin >> vec.at(i);
        mx = max(mx,vec.at(i));
    }
    for(int i = 0;i<N;i++){
    
    n = n + vec.at(i)*vec.at(i);
    m = m + (-2)*vec.at(i);
    }

    long long mi;
    for(int i = 1;i <= mx;i++){
        
        ans = n + m*i + (N*i*i);
        
        if(i == 1){
            mi = ans;
        }else{
        mi = min(mi,ans);
        }
    }
    cout << mi << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

int main() {
  ll n;
  cin >> n;
  vec w(n),s(n),v(n);
  vector<pll> a(n);
  for(ll i=0;i<n;i++) {
    cin >> w[i] >> s[i] >> v[i];
    a[i]={w[i]+s[i],i};
  }
  sort(a.begin(),a.end());
  mat dp(n+1,vec(2e4+10));
  for(ll i=0;i<n;i++) {
    ll idx=a[i].second;
    for(ll j=0;j<=2e4;j++) {
      dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
      if(j) dp[i+1][j]=max(dp[i+1][j],dp[i+1][j-1]);
      if(j<=s[idx]&&j+w[idx]<=2e4) {
        dp[i+1][j+w[idx]]=max(dp[i+1][j+w[idx]],dp[i][j]+v[idx]);
      }
    }
  }
  cout << dp[n][2e4] << endl;
}

Measured memory_bytes: 163696
#include <stdio.h>
//#include <math.h>
//#include <string.h>
#include <ctype.h>
#include <stdlib.h>

int main(){
	long long n, d[10010], i, MIN = 1000000, MAX = -1000000, sum = 0;
	scanf("%lld",&n);
	for(i = 0; i < n; i++){
		scanf("%lld", &d[i]);
		sum += d[i];
		if(MIN > d[i]) MIN = d[i];
		if(MAX < d[i]) MAX = d[i];
	}
	printf("%lld %lld %lld\n",MIN,MAX,sum );
	return 0;
}

Measured memory_bytes: 676
#include<stdio.h>
int a[55] = { 2, 3, 13, 23, 43, 53, 73, 83, 103, 113, 163, 173, 193, 223, 233, 263, 283, 293, 313, 353, 373, 383, 433, 443, 463, 503, 523, 563, 593, 613, 643, 653, 673, 683, 733, 743, 773, 823, 853, 863, 883, 953, 983, 1013, 1033, 1063, 1093, 1103, 1123, 1153, 1163, 1193, 1213, 1223, 1283 };
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n-1;i++) {
		printf("%d ", a[i]);
	}
	printf("%d\n",a[n-1]);
}

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

int N;
string S;
int Macc[1000100];
int Cacc[1000100];
int MC[1000100];
int MCacc[1000100];
int Q;

signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N;
    cin >> S;
    Macc[0] = 0;
    Cacc[0] = 0;
    rep(i, N) {
        if (S[i]=='M') Macc[i+1] = Macc[i]+1;
        else Macc[i+1] = Macc[i];
        if (S[i]=='C') Cacc[i+1] = Cacc[i]+1;
        else Cacc[i+1] = Cacc[i];
    }
    MCacc[0] = 0;
    rep(i, N) {
        if (S[i]=='C') MC[i] = Macc[i];
        else MC[i] = 0;
        MCacc[i+1] = MCacc[i]+MC[i];
    }
    
    cin >> Q;
    while (Q--) {
        int k; cin >> k;
        int ans = 0;
        int M = 0;
        rep(i, N) {
            int j = min(N, i+k);
            if (S[i]=='D') ans += MCacc[j]-MCacc[i+1]-(Cacc[j]-Cacc[i+1])*M;
            else if (S[i]=='M') M++;
        }
        cout << ans << endl;
    }
}

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

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

  sort(A.begin(), A.end(), greater<int>());

  priority_queue<int> pq;
  for (int i = 0; i < N; ++i)
    pq.push(A[i]);

  for (int i = 0; i < M; ++i) {
    int AA = pq.top();
    pq.pop();
    pq.push(AA / 2);
  }

  long long ans = 0;
  for (int i = 0; i < N; ++i) {
    ans += pq.top();
    pq.pop();
  }

  cout << ans << endl;
}

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

int main() {
    int K,S;
    int cnt=0;
    cin >> K >> S;
    for(int i=0;i<=K;i++){
        for(int j=0;j<=K;j++){
            int k = S - i - j;
            if(k<=K&&k>=0){
                //cout << i <<" "<< j <<" "<< k << endl;
                cnt++;
            }
        }
    }
    cout << cnt << endl;
}

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

using P = pair<int, int>;
int H, W;
vector<vector<char>> maze;  // 迷路の内容を保存する配列
vector<vector<int>> dist;   // 距離を記録しておく配列
P s, g;

const int INF = 1e8;
// 幅優先探索
void bfs(P s) {
    dist.assign(H, vector<int>(W, INF));  // 初期化

    queue<pair<int, int>> que;
    que.emplace(s);
    dist[s.first][s.second] = 0;
    while (que.size() != 0) {
        pair<int, int> now = que.front();
        que.pop();
        int dy[4] = {0, 0, 1, -1};  // dx,dy は次の探索場所への距離を表す（４方向分）
        int dx[4] = {1, -1, 0, 0};
        for (int i = 0; i < 4; i++) {
            int ny = now.first + dy[i];
            int nx = now.second + dx[i];
            if (ny < 0 || H <= ny || nx < 0 || W <= nx) continue;
            if (maze[ny][nx] == '#') continue;  // 障害物があればスルー
            if (dist[ny][nx] != INF) continue;
            que.push(make_pair(ny, nx));
            dist[ny][nx] = dist[now.first][now.second] + 1;
        }
    }
}

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

    cin >> H >> W;
    s = make_pair(0, 0);
    g = make_pair(H - 1, W - 1);

    int cnt = 0;
    maze.assign(H, vector<char>(W, '.'));  // 初期化
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> maze[i][j];
            if (maze[i][j] == '#') cnt++;
        }
    }

    bfs(s);
    if (dist[g.first][g.second] == INF) {
        cout << -1 << endl;
    } else {
        cout << H * W - cnt - dist[g.first][g.second] - 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

A, B = LI()
ans = mod
for i in range(1251):
    if math.floor(i * 0.08) == A and math.floor(i * 0.1) == B:
        ans = i
        break
    else:
        pass
else:
    ans = -1

print(ans)


Measured memory_bytes: 65004
using System;
using System.Collections.Generic;
using System.Linq;
public class Hello
{
    public static void Main()
    {
        //入力を保持する
        var input = Console.ReadLine().Split().Select(v => int.Parse(v)).ToArray();
        var heads = input[0];
        var legs = input[1];

        var tempHeads = legs / 4;
        var tempLegs = legs % 4;

        if ((tempHeads == 0 && tempLegs == 2) && (heads == 1))
        {
            Console.WriteLine("Yes");
            return;
        }
        else if((tempHeads == 1 && tempLegs == 0) && (heads == 1))
        {
            Console.WriteLine("Yes");
            return;
        }
        else if ((tempHeads == heads && tempLegs == 0))
        {
            Console.WriteLine("Yes");
            return;
        }
        if (tempLegs % 2 == 1)
        {
            Console.WriteLine("No");
            return;
        }
        else
        {
            if (tempLegs == 2 && tempHeads ==24 && heads == 25)
            {
                Console.WriteLine("Yes");
                return;

            }
        }


        while (true)
        {
            tempHeads = tempHeads - 1;
            tempLegs = tempLegs + 4;
            if (tempHeads + (tempLegs / 2) == heads)
            {
                Console.WriteLine("Yes");
                return;
            }
            if (tempHeads == 0)
            {
                break;
            }
        }
        Console.WriteLine("No");

    }
}




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

int main() {
	int N;
	cin >> N;
	map<string, ll> m;
	string s;
	ll result = 0;

	repeat(i, N) {
		cin >> s;
		int n = 0;
		sort(s.begin(), s.end());
		m[s] += 1;
	}

	for(auto& p : m) {
		ll count = p.second;
		result += count * (count-1) / 2;
  }

	cout << result << endl;
	return 0;
}

Measured memory_bytes: 11136
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
//#include<cstdio>//"scanf("%lf",&(double));printf("%f",(double));"
//#include<iomanip>//"cout<<fixed<<setprecision(n)<<sth<<endl;"
//#include<string>//"reverse(s's it,s's it)"
//#include<functional>//"greater<T>" "sort(a,a+n,greater<int>());""
//#include<cmath>//"abs" "sqrt"
//#include<numeric>//"accumulate(inputit,inputit,init,(optional) object)"
//#include<algorithm>//"lower_bound(it,it,v)" "next_permutation(a,a+n)"
//"reverse(v's it,v's it)"(v: vector)
//#include<cassert>//"assert(cond);": error if cond doesn't hold.
using namespace std;
#define pb push_back//also for STRING
#define fi first
#define sc second
#define mp make_pair
#define is insert//also use as v.is(v's it,w's it,w's it);//Be careful in topcoder
#define ps push//stack,(priority) queue,//Be careful in topcoder.
#define fr front//queue//for priority, use top().//Be careful in topcoder.
typedef long long ll;//not necessarily//Be careful in topcoder.
typedef pair<int,int> pii;//Be careful in topcoder.
//Add other types in the same way.
const ll M = 1000000007;//can be changed
ll mod(ll a){	return (a + M) % M;	}//M can be a variable
void plmod(ll &a,ll b){	a = (a + b + M) % M;	return;	}
void mnmod(ll &a,ll b){	a = (a - b + M) % M;	return;	}
void mlmod(ll &a,ll b){	a = (a * b) % M;  	return;	}
//Caution! you may need sth larger than "+M"!
void chmax(int &a,int b){	a = max(a, b);	return;	}
void chmin(int &a,int b){	a = min(a, b);	return;	}
//These 2 could be better in long long

int main(){
    ll s;
    cin>>s;
    cout<<"0 0 1000000000 1 ";
    if(s % 1000000000 == 0){
        cout<<"0 "<<s/1000000000<<endl;
    }else{
        ll t = (s/1000000000)+1;
        cout<<1000000000*t - s <<" "<<t<<endl;
    }
}

//for Google Code Jam
//void solve(){
//
//}
//
//int main(){
//	int Q;
//	scanf("%d",&Q);
//	for(int q=1;q<=Q;++q){
//		printf("Case #%d: ",q);
//		solve();
//	}
//}

//for topcoder
//class nameofclass{
//public:
//	T nameoffunction(){
//
//	}
//};


Measured memory_bytes: 256
# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a = [int(ipti()) for _ in range(n)]
    ans = 0

    for i in range(n):
        ans += a[i] // 2
        if a[i] % 2 == 1 and i != (n-1) and a[i+1] > 0:
            ans += 1
            a[i+1] -= 1

    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 44252
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back

#define eprintf(...) fprintf(stderr, __VA_ARGS__)

const int maxn = 2e5 + 5;
int mx[maxn];
int n, a[maxn];

void upd(int x, int v) {
	for (; x < maxn; x += x & -x) mx[x] = max(mx[x], v);
}

int qry(int x) {
	int ans = 0;
	for (; x; x -= x & -x) ans = max(ans, mx[x]);
	return ans;
}

struct T {
	int val, lst, fix;
	T *ls, *rs;
	T(int v) {val = lst = v, fix = rand(), ls = rs = NULL;}
	void pu() {lst = rs ? rs->lst : val;}
};

void split(T *x, int v, T *&a, T *&b) {
	if (!x) {a = b = NULL; return ;}
	if (x->val <= v) a = x, split(x->rs, v, a->rs, b), a->pu();
	else b = x, split(x->ls, v, a, b->ls), b->pu();
}

T *merge(T *a, T *b) {
	if (!a || !b) return a ? a : b;
	if (a->fix < b->fix) {a->rs = merge(a->rs, b), a->pu(); return a;}
	else {b->ls = merge(a, b->ls), b->pu(); return b;}
}

void prt(T *x) {if (x) prt(x->ls), printf("%d ", x->val), prt(x->rs);}

T *rt[maxn * 2];
vector <int> lst;
int f[maxn];

int main() {
//	freopen("in", "r", stdin);
	scanf("%d", &n);
	for (int i = 0; i < n; ++ i) scanf("%d", &a[i]);
	for (int i = 0; i < n; ++ i) {
		int v = qry(n - a[i] + 1);
		rt[v] = merge(rt[v], new T(a[i]));
		f[a[i]] = v;
		upd(n - a[i] + 1, v + 1);
	}
	lst.resize(qry(n));
	for (int i = 0; i < lst.size(); ++ i) lst[i] = rt[i]->lst;
	for (int i = 0; i < lst.size() - 1; ++ i) {
		while (rt[i]) {
			int x = rt[i]->lst;
			int lb = i + 1, rb = lst.size();
			while (lb < rb) {
				int md = (lb + rb) >> 1;
				if (lst[md] > x) lb = md + 1;
				else rb = md;
			}
			if (lb == lst.size()) lst.pb(0);
			T *a, *b;
			split(rt[i], lst[lb], a, b);
			rt[i] = a; rt[lb] = merge(rt[lb], b);
			lst[i] = a ? a->lst : 0; lst[lb] = rt[lb]->lst;
		}
	}
	printf("%d\n", int(lst.size()) - 1);
//	printf("%.3f\n", clock() * 1.0 / CLOCKS_PER_SEC);
	return 0;
}


Measured memory_bytes: 16128
#D問題
N,A,B = map(int,input().split())
X = list(map(int,input().split()))
ans = 0
now = 0
for i in range(N):
    if i == 0:
        now = X[0]
    else:
        ans += min((X[i]-now)*A,B)
        now = X[i]
print(ans)

Measured memory_bytes: 62704
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

readInt = readLn :: IO Int
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readNInts = readInt >>= flip replicateM readInt

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

main = do
	getLine
	as <- readInts
	bs <- readInts
	print $ solve as bs

solve _ [] = 0
solve (a:a':as) (b:bs) = d1 + d2 + solve ( a' - d2 : as ) bs
	where
		d1 = min a b
		rest = b - d1
		d2 = min a' rest

Measured memory_bytes: 5756
# coding: utf-8
# Your code here!

N, M = (int(i) for i in input().split()) 
AB=[list(map(int,input().split())) for _ in range(N)]
# print(AB)
AB.sort()
# print(AB)

money = 0
for a, b in AB:

    # print(M) 
    if M==0:
        break
    elif b < M:
        # print(a*xb)
        money += a*b
        M -= b
    elif b >= M:
        # print(M)
        money += M*a
        M = 0
    # print(M, money)
print(money)
        

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

using namespace std;
typedef long long ll;
typedef long int li;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1LL<<60;

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

int main(){

  string s;cin>>s;

  ll win=0;
  rep(i,0,s.size()){
    if(s[i]=='o')win++;
  }

  if(win+15-s.size()>=8)out("YES");
  else out("NO");




  return 0;
}


Measured memory_bytes: 256
($n,$m)=glob<>;$d=1e9+7;
if(abs($n-$m)>1){
    print"0";
    exit;
}
$o=1+($n==$m);
$o=$o*$_%$d for (1..$n);
$o=$o*$_%$d for (1..$m);
print $o


Measured memory_bytes: 768
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cstdint>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <chrono>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <utility>
#include <limits>
#include <list>
#include <type_traits>

/* template start */

using i64=std::int_fast64_t;
using u64=std::uint_fast64_t;
 
#define rep(i, a, b) for (i64 i = (a); (i) < (b); (i)++)
#define all(i) i.begin(), i.end()

#ifdef LOCAL
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out(){std::cerr<<std::endl;}

template<typename Head,typename... Tail>
void debug_out(Head h,Tail... t){
  std::cerr<<" "<<h;
  if(sizeof...(t)>0)std::cout<<" :";
  debug_out(t...);
}
 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (std::size_t i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}

template<typename Num>
constexpr Num mypow(Num a, u64 b,Num id=1) {
  if(b==0)return id;
  Num x = id;
  while (b > 0) {
    if(b & 1)x*=a;
    a*=a;
    b >>= 1;
  }
  return x;
}

/* template end */

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

  i64 n;
  std::cin>>n;

  std::string s;
  std::cin>>s;

  i64 red=0;
  rep(i,0,n)if(s[i]=='R')red++;

  i64 ans=red;
  i64 cnt=0;

  rep(i,0,n){
    if(s[i]=='R')cnt++;
    chmin(ans,std::max(i+1-cnt,red-cnt));
  }

  std::cout<<ans<<"\n";
  
  return 0;
}

Measured memory_bytes: 3768
# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a = list(map(int, readline().split()))

    cntr = Counter(a)
    tsum = 0

    for key, value in cntr.items():
        temp = (value - 1) * value // 2
        tsum += temp

    for i in range(n):
        k = a[i]
        v = cntr[k]
        print(tsum-(v-1))


if __name__ == '__main__':
    main()


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

int main(){
	int N;
	cin >> N;
	vector<ll> A(N);
	int cnt = 0;
	rep(i,N){ cin >> A[i]; if(A[i]<=0)cnt++; }

	ll ans = 0;
	rep(i,N){ ans += abs(A[i]); A[i] = abs(A[i]); }
	if(cnt%2 == 1){ ans -= *min_element(A.begin(),A.end())*2; }
	cout << ans << endl;
}


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

int main()
{
int n;
  cin>>n;
  
  long long arr[n];
  long long ans=1;
  for(int i=0;i<n;i++)
  {
    cin>>arr[i];
  }
  int count=0;
  for(int i=0;i<n;i++)
  {
      if(arr[i]==0)
      count++;
  }
  if(count>0)
  {
      cout<<0;
      return 0;
  }
  for(int i=0;i<n;i++)
  {
 
    if(arr[i]<= 1000000000000000000/ans)
    {
      ans*=arr[i];
    }
    else
    {
        
        cout<<-1;
        return 0;
    }
  }
 cout<<ans;
  
}

Measured memory_bytes: 4392
#include<bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n ; i++)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x) // decltypeで型取得、引数があればva_argsのところに入れる
using namespace std;
typedef long long ll; // long longをllでかけるようにした
const int INF = 1e9;

int main(void){
    int n; cin >> n;
    int year = 19 * 5 + 20 * 5, year3 = 20 * 10;
    REP(i, n){
        int y, m, d; cin >> y >> m >> d;
        int san = 1000 / 3 - y / 3;
        int ans = (1000 - (y + 1) - san) * year + san * year3 + 1;
        if(y % 3 == 0){
            ans += (10 - m) * 20 + (20 - d);
        }
        else{
            if(m % 2 != 0) ans += ((10 - m) / 2) * 39 + 19 + (20 - d);
            else ans += ((10 - m) / 2) * 39 + (19 - d);
        }
        cout << ans << endl;
    }
}


Measured memory_bytes: 3040
N, K = [int(_) for _ in input().split()]
H = [int(_) for _ in input().split()]

memo = [1e12] * (N + 1)
memo[0] = 0

for i in range(N - 1):
    for j in range(1, K + 1):
        if i + j >= N: break
        memo[i + j] = min(abs(H[i] - H[i + j]) + memo[i], memo[i + j])
print(memo[N - 1])


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

int main() {

  int N;
  cin >> N;

  char arare_c;
  int is_four = 0;
  for (int i=0; i<N; i++) {
    cin >> arare_c;

    if (arare_c == 'Y')
      is_four = 1;
  }

  if (is_four)
    cout << "Four" << endl;
  else
    cout << "Three" << endl;
}

Measured memory_bytes: 256
// When you are hungry for something and you're determined and you're focused 
// and you're committed to something it's hard to surrender, isn't it?

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ll long long 
#define int ll
#define mod 1000000007
#define mod1 1000000006
#define modi 998244353
#define setbit(x) __builtin_popcount(x)
#define fff(i,n) for(int i=0;i<n;i++)
#define ff first
#define ss second
#define pb push_back
vector<ll> vi[300005];
int color[100005];
ll pa[500005];
ll si[500005];
#define pb push_back
bool visi[1000005]={false};
bool is[100005];
ll fac[10000001];
ll prime[400005];
ll bit[100005];
const long double eps = 1.0e-14;      // allowable error
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL);
 
 
void fact(){
    fac[0]=1;
    for(int i=1;i<=10000000;i++){
        fac[i]=(fac[i-1]*i)%mod;
    }
    return ;
}
void sieve(){
    prime[0]=0;
    prime[1]=0;
    for(int i=2;i<400005;i++){
        prime[i]=1;
    }
    for(int i=2;i*i<400005;i++){
        if(prime[i]==1){
            for(int j=i*i;j<400005;j+=i){
                prime[j]=0;
            }
        }
    }
    
}
 
ll power(ll n , ll p ){
    if(p==0)
        return 1;
    
    ll res = power((n*n)%mod,p/2);
    if(p%2==1)
        res = (n*res)%mod;
    
    return res;
}
 
 
void upd(ll i,ll val,ll n) {
    for(;i<=n;i+=i&(-i))
        bit[i]+=val;
}
 
ll qry(ll i) {
    ll sum=0;
    for(;i>0;i-=i&(-i))
        sum+=bit[i];
    return sum;
}
 
 
ll fin(ll u) {
    if(pa[u]==u)
        return u;
    return fin(pa[u]);
}
 
void uni(ll u,ll v) {
    ll p1=fin(u);
    ll p2=fin(v);
    if(p1==p2)
        return;
    if(si[p1]<si[p2])
        swap(p1,p2);
    si[p1]+=si[p2];
    pa[p2]=p1;
    return;
}
 
int32_t main() {
    fio
    
    int n;
    cin >> n;
    int a[n+1],b[n];
    fff(i,n+1)
    cin >> a[i];
    fff(i,n)
    cin >> b[i];
    
    int ans=0;
    fff(i,n) {
        if(a[i]>=b[i]) {
            ans+=b[i];
        }
        else {
            ans+= a[i];
            b[i]-=a[i];
            if(a[i+1]>=b[i]) {
            ans+=b[i];
            a[i+1]-=b[i];
            }
            else{
            ans+=a[i+1];
            a[i+1]=0;
            }
        }
    }
    
    cout << ans;
    
	return 0;
    
}

Measured memory_bytes: 10496
while(1):
    n, m = map(int,raw_input().split())
    if n == 0 and m == 0:
        break
    
    agree_sum = [0]*m
    for i in range(n):
        agree_sum = [ x+y for (x, y) in zip(agree_sum, map(int,raw_input().split())) ]
    
    for i in range(m):
        if max(agree_sum) == -1:
            break;
        max_idx = agree_sum.index(max(agree_sum))
        agree_sum[max_idx] = -1
        print max_idx+1,
    print

Measured memory_bytes: 4244
N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split()))for _ in range(Q)]
l = [lr[i][0] for i in range(Q)]
r = [lr[i][1] for i in range(Q)]
#print(lr)
#print(l)
#print(r)

c = [0] * N
cnt = 0

for i in range(N-1):
    if S[i:i+2] == 'AC':
        c[i+1]=c[i]+1
    else:
        c[i+1]=c[i]
    #c[i] = S[:i].count('AC')
    #countを使わずにiまでの合計値をリスト化

#print(c)

for i,j in zip(l,r):
    #print(sum(c[:j])-sum(c[:i]))
    #l,r = map(int,input().split())
    print(c[j-1]-c[i-1])
    #合計値を利用してsumを使わずに差を表示して計算減させる
    #リストを要素ごとに分けるのは初めにやっておいて大丈夫

Measured memory_bytes: 31376
N = int(input())
s = [0]*N

for i in range(N):
	s[i] = int(input());

s = sorted(s)

res = sum(s)
find = False
if res % 10 == 0:
	for cs in s:
		if cs % 10 == 0:
			continue
		else:
			find = True
			res -= cs
			break
else:
	find = True
print(res if find == True else 0)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<n; i++)
#define pb push_back
#define int long long
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int N;
string S;

signed main() {
    //cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> S;
    int ans = 0;
    rep(i, N+1) {
        string X = S.substr(0, i);
        string Y = S.substr(i, N-i);
        int ans_cand = 0;
        rep(j, 26) {
            bool f1 = false, f2 = false;
            rep(k, i) if (X[k]-'a'==j) f1 = true;
            rep(k, N-i) if (Y[k]-'a'==j) f2 = true;
            if (f1&&f2) ans_cand++;
        }
        ans = max(ans, ans_cand);
    }
    cout << ans << endl;
}

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

int main()
{
    int a,b;
    cin>>a>>b;
    if((a+b)%2==0)
    {
        cout<<(a+b)/2<<endl;
    }
    else
    {
        cout<<(a+b)/2 +1<<endl;
    }
    
    return 0;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

// conversion number to bit
string num2bit(ll num, ll len){
  string bit = "";
  REP(i, len){
    bit += char('0'+(num>>i & 1));
  }
  return bit;
}

ll dp[303][303];

ll rec(ll l, ll r, vector<ll> &w){
	if(dp[l][r]>=0) return dp[l][r];
	if(l>=r){
		dp[l][r] = 0;
		return 0;
	}
	if(l+1==r){
		dp[l][r] = 1;
		return 1;
	}

	ll res = rec(l+1, r-1, w);
	if(res != 0 || abs(w[l]-w[r-1])>1){
		res += 2;
	}

	for(int m=l+1;m<r;m++){
		ll tmp1 = rec(l, m, w);
		ll tmp2 = rec(m, r, w);
		chmin(res, tmp1+tmp2);
	}

	dp[l][r] = res;
	return res;
}

void solve(){
	ll n;
	cin >> n;
	if(n==0) exit(0);
	vector<ll> w(n);
	REP(i, n) cin >> w[i];

	REP(i, 303)REP(j, 303) dp[i][j] = -1;

	ll tmp = rec(0, n, w);

	/*
	REP(i, n+1){
		REP(j, n+1){
			cerr << dp[i][j] << " ";
		}
		cerr << endl;
	}
	*/

	cout << n-tmp << endl;
}

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

    while(1){
    	solve();
    }
    return 0;
}


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

int main(void) {
  int n;
  cin >> n;
  map<char,long long> dic;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    dic[s[0]]++;
  }

  string s = "MARCH";
  long long ret = 0;
  for (int i = 0; i < 5; i++) {
    for (int j = i + 1; j < 5; j++) {
      for (int k = j + 1; k < 5; k++) {
        ret += dic[s[i]] * dic[s[j]] * dic[s[k]];
      }
    }
  }
  cout << ret << endl;
  return 0;
}

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

int main(){

ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,i,sum=0;
    cin>>n;
    int a[n+1],b[n+1],c[n+1];
    for(i=1;i<=n;i++)
    cin>>a[i];
    for(i=1;i<=n;i++)
    cin>>b[i];
    for(i=1;i<=n-1;i++)
    cin>>c[i];
    for(i=1;i<=n;i++)
    {
    	if(i==1)
    	{
    		sum=sum+b[a[i]];
    		
		}
		else
		{
			if(a[i]-a[i-1]==1)
			{
				sum=sum+b[a[i]]+c[a[i-1]];
				
				
			}
			else
			sum=sum+b[a[i]];
		}
	}
	cout<<sum;
     
}

Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

using lint = long long;
using P = pair<int, int>;
using LLP = pair<long long, long long>;

#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define reps(i, n) for(int i = 1, i##_len = (int)(n) ; i <= i##_len ; ++i)
#define rrep(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define rreps(i, n) for(int i = (int)(n) ; i > 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())
#define REVERSE(x) reverse((x).begin(), (x).end())
#define TWINS(x) cout << ((x) ? "Yay!" : ":(") << '\n'
#define endl '\n'

constexpr int IINF = (1 << 30) - 1;
constexpr long long LLINF = 1LL << 61;
constexpr double EPS = 1e-10;

constexpr int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
constexpr int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

template<typename T>
bool chmax(T& a, T b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}

template<typename T>
bool chmin(T& a, T b){
    if(b < a){
        a = b;
        return true;
    }
    return false;
}

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

    lint h;
    cin >> h;

    lint ans = 0;
    lint k = 1;
    while(h > 0LL){
        ans += k;
        h /= 2LL;
        k *= 2LL;
    }

    cout << ans << endl;

    cout << flush;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

struct union_find {
    vector<int> parent; //親の番号を格納する。親だった場合は-(その集合のサイズ)
    union_find(int N) {
        parent = vector<int>(N, -1); //parentの値を-1にする(すべてバラバラ)
     }
    int root(int A) { //Aがどのグループに属しているか調べる
        if (parent[A] < 0) return A;
        return parent[A] = root(parent[A]);
    }
    int size(int A) { //自分のいるグループの頂点数を調べる
        return -parent[root(A)];//親をとってきたい
    }
    bool connect(int A, int B) { //AとBをくっ付ける．すでにつながっていた場合false
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) return false; //すでにくっついてるからくっ付けない
        if (size(A) < size(B)) swap(A, B); //大小が逆だったらひっくり返しちゃう。
        parent[A] += parent[B]; //Aのサイズを更新する
        parent[B] = A; //Bの親をAに変更する
        return true;
    }
};

int main(void)
{
    int N,M;
    cin >> N >> M;
    vector<int> p(N);
    for (int i = 0; i < N; i++) {
        cin >> p[i];
        p[i]--;
    }
    union_find uf(N);
    REP(i, M){
        int x,y;
        cin >> x >> y;
        x--;y--;
        uf.connect(x,y);
    }

    int ans = 0;
    REP(i, N){
        if(uf.root(p[i]) == uf.root(i)) ans++;
    }

    pr(ans);
}

Measured memory_bytes: 1024
import typing

def binary_serch(x:int, b_sum:list):
    l = 0
    r = len(b_sum) - 1
    mid = (l + r + 1) // 2
    res = mid
    while True:
        if x == b_sum[mid]:
            return mid
        elif x < b_sum[mid]:
            res = mid - 1
            r = mid
            mid = (l + r + 1) // 2
        elif b_sum[mid] < x:
            res = mid 
            l = mid
            mid = (l + r + 1) // 2
        if l + 1 == r:
            return res

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
b_sum = [0] * (m + 2)
for i in range(m):
    b_sum[i + 1] = b[i] + b_sum[i]

b_sum[-1] = 10 ** 9 + 1
a = [0] + a
pass_k = 0
ans = 0
for i in range(n + 1):
    if pass_k + a[i] <= k:
        pass_k += a[i]
        book = i
        book += binary_serch(k - pass_k, b_sum)
        ans = max(ans, book)
    else:
        break

print(ans)

Measured memory_bytes: 40956