akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

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

int m, n, l;
int tot;
int id[N][N];
long long c[N];

struct Mat
{
	int a[N][N];
	void clear() {
		memset(a, 0, sizeof a);
	}
};

int valid(int x, int y)
{
	return x >= 0 && y >= 0 && id[x][y] >= 0;
}

Mat operator * (const Mat &a, const Mat &b)
{
	Mat ret;
	for(int i = 0; i < tot; ++ i) {
		for(int j = 0; j < tot; ++ j) {
			ret.a[i][j] = 0;
			for(int k = 0; k < tot; ++ k) {
				ret.a[i][j] = (ret.a[i][j] + (long long)a.a[i][k] * b.a[k][j]) % m;
			}
		}
	}
	return ret;
}

Mat operator ^ (Mat a, int l)
{
	Mat ret;
	ret.clear();
	for(int i = 0; i < tot; ++ i) {
		ret.a[i][i] = 1;
	}
	for( ; l; l >>= 1, a = a * a) {
		if (l & 1)
			ret = ret * a;
	}
	return ret;
}

void solve()
{
	tot = 0;
	int cur = n;
	memset(id, -1, sizeof id);
	for(int i = 0; i < n; ++ i) {
		for(int j = 0; j < cur; ++ j) {
			id[i][j] = tot ++;
		}
		cur ++;
	}
	-- cur;
	for(int i = 0; i < n - 1; ++ i) {
		for(int j = i + 1; j < cur; ++ j) {
			id[i + n][j] = tot ++;
		}
	}

	Mat a;
	a.clear();
	for(int i = 0; i < 2 * n; ++ i) {
		for(int j = 0; j < 2 * n; ++ j) {
			if (id[i][j] >= 0) {
				a.a[id[i][j]][id[i][j]] ++;
				for(int d = 0; d < 6; ++ d) {
					int ni = i + dx[d];
					int nj = j + dy[d];
					if (valid(ni, nj)) {
						a.a[id[i][j]][id[ni][nj]] ++;
					}
				}
			}
		}
	}

	/*
	cout << "!!" << endl;
	for(int i = 0; i < tot; ++ i) {
		for(int j = 0; j < tot; ++ j) {
			cout << a.a[i][j] << ' ';
		}
		cout << endl;
	}
	cout << "!!" << endl;
	for(int i = 0; i < tot; ++ i) {
		for(int j = 0; j < tot; ++ j) {
			cout << a.a[i][j] << ' ';
		}
		cout << endl;
	}
	*/
	a = a ^ l;

	int x;
	memset(c, 0, sizeof c);
	for(int i = 0; i < tot; ++ i) {
		scanf("%d", &x);
		for(int j = 0; j < tot; ++ j) {
			(c[j] += (long long)x * a.a[i][j]) %= m;
		}
	}
	long long ret = 0;
	for(int i = 0; i < tot; ++ i) {
		ret += c[i];
	}
	cout << ret << endl;
}

int main()
{
	int test = 0;
	for( ; cin >> n >> m >> l && (n || m || l); ) {
		printf("Case %d: ", ++ test);
		solve();
	}
}

Measured memory_bytes: 1472
/*
 * main.c
 *
 *  Created on: 2019/05/25
 *      Author: family
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main()
{
	int r = 0, D = 0, x = 0, ans = 0;
	int i = 0;
	scanf("%d %d %d", &r, &D, &x);
	for(i = 0; i < 10; i++) {
		ans = (r * x) - D;
		printf("%d\n",ans);
		x = ans;
	}
    return 0;
}


Measured memory_bytes: 128
n=int(input())
A=list(map(int,input().split()))
count=0
i=0
while i < n:
    j=i
    while j < n-1 and A[j]<=A[j+1]:
        j += 1
    k=i
    while k < n-1 and A[k]>=A[k+1]:
        k += 1
    count += 1
    i = max(j,k)+1
print(count)

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

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

int main(){
  ll x,y;
  cin >> x >> y;

  if(x*y>=0&&x<=y) cout << y-x;
  else if(x*y>0&&x>y) cout << x-y+2;
  else cout << abs(abs(x)-abs(y))+1;
}

Measured memory_bytes: 3636
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(a) (a).begin(), (a).end()

#define INF 1000000000

using namespace std;

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

    int K;
    cin >> K;

    vector<string> res;

    for (int i = 0; i < s.size(); i++) {
        for (int j = 1; j <= K; j++) {
            res.push_back(s.substr(i, j));
        }
    }

    sort(ALL(res));
    res.erase(unique(ALL(res)), res.end());

    cout << res[K - 1] << endl;

    return 0;
}


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

int main() {
  string s;
  cin >> s;
  reverse(s.begin(), s.end());
  int d = s.size();
  vector<int> n(d);
  for (int i = 0; i < d; i++) n.at(i) = s.at(i) - '0';
  n.push_back(0);
  vector<int> dp0(d + 1), dp1(d + 1);
  dp0.at(0) = n.at(0);
  dp1.at(0) = 10 - n.at(0);
  for (int i = 1; i <= d; i++) {
    dp0.at(i) = min(dp0.at(i - 1) + n.at(i), dp1.at(i - 1) + n.at(i) + 1);
    dp1.at(i) = min(dp0.at(i - 1) + (10 - n.at(i)), dp1.at(i - 1) + (9 - n.at(i)));
  }
  cout << min(dp0.at(d), dp1.at(d)) << endl;
}


Measured memory_bytes: 14784
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
#define int long long
#define pb push_back
#define fi first
#define se second
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define IO ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define sz(x) (int)x.size()
const int mod = 1e9 + 7;
const int mod1 = 998244353;
typedef long double f80;

#ifndef LOCAL
#pragma GCC optimize ("O2")
#define endl '\n'
#endif

template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}

ll pwr(ll a,ll b, ll mod){
    a %= mod;
    int ans = 1;
    while(b){
        if(b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() { cerr << endl; }

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

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

const int N = 2e5 + 5;
int a[N];
void solve(){
	int n;
	cin >> n;
	int cnt[20] = {0};
	int pt = 1;
	int ans = 0;
	fr(i, 1, n){
		cin >> a[i];
		fr(j, 0, 19){
			cnt[j] += (a[i] >> j) & 1;
		}
		while(1){
			bool good = 1;
			fr(j, 0, 19){
				if(cnt[j] > 1){
					good = 0;
					break;
				}
			}
			if(good) break;
			fr(j, 0, 19){
				cnt[j] -= (a[pt] >> j) & 1;
			}
			pt++;
		}
		ans += (i - pt + 1);
	}
	cout << ans;
}
signed main(){
    IO;
    #ifdef LOCAL
        freopen("inp.txt","r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    cout << setprecision(10) << fixed;
    int t = 1;
    // cin >> t;
    fr(tt, 1, t){
        solve();
    }
    return 0;
}

Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		loop: while (true) {
			long a = scanner.nextInt();
			String op = scanner.next();
			long b = scanner.nextInt();
			
			switch (op) {
			case "+":
				System.out.println(a + b);
				break;

			case "-":
				System.out.println(a - b);
				break;

			case "*":
				System.out.println(a * b);
				break;

			case "/":
				System.out.println(a / b);
				break;

			case "?":
				break loop;
			}
		}

		scanner.close();
	}

}



Measured memory_bytes: 26192
fun main(args: Array<String>) {
    val (a,b,c) = readLine()!!.split(" ").map { it.toByte() }

    val res = if(a==b && b==c) {
        "No"
    }else if(a!=b && b!=c && c!=a) {
        "No"
    }else if(a==b && b!=c) {
        "Yes"
    }else if(b==c && a!=c) "Yes" else "Yes"

    println(res)
}

Measured memory_bytes: 38048
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = Integer.parseInt(sc.next());
		int B = Integer.parseInt(sc.next());
		sc.close();
		int sum = A + B;
		if(sum % 2 == 0) {
			System.out.println(sum / 2);
		}else {
			System.out.println("IMPOSSIBLE");
		}
	}
}

Measured memory_bytes: 21844
#include <stdio.h>
#define M 100000
int R[100],C[100][100];
int n;
 
void MatrixChainMultiplication()
{
  int i,j,k,l,cost;
  for(i=1;i<=n;i++)
    {
      C[i][i]=0;
    }
  for(l=2;l<=n;l++)
    {
      for(i=1;i<=n-l+1;i++)
    {
      j=i+l-1;
      C[i][j]=M;
      for(k=i;k<=j-1;k++)
        {
          cost=C[i][k]+C[k+1][j]+R[i-1]*R[k]*R[j];
          if(cost<C[i][j])
        {
          C[i][j]=cost;
        }
        }
    }
    }
  printf("%d\n",C[1][n]);
}
 
 
 
 
main(){
  int i,r,c;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    {
      scanf("%d %d",&r,&c);
      R[i]=r;
      R[i+1]=c;
    }
  MatrixChainMultiplication();
  return 0;
}

Measured memory_bytes: 636
#!/usr/bin python3
# -*- coding: utf-8 -*-

# 区間スケジューリング問題
# 区間の集合の中から、重ならないように最大で何個選べるかを問う問題である。
# 区間を「終端が早い順」にソートして、とれる順にとる Greedy で解くことができる。
# XL<-区間の集合

def main():
    N = int(input())
    XL = [None] * N
    for n in range(N):
        X, L = map(int,input().split())
        XL[n] = (X-L,X+L)
    XL.sort(key=lambda x:x[1])
    ret = 0
    TMP = XL[0][0]
    for x in XL:
        if TMP <= x[0]:
            TMP = x[1]
            ret += 1
    print(ret)

if __name__ == '__main__':
    main()

Measured memory_bytes: 18260
// rust input macro: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}
 
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
 
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}
 
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
 
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
 
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
 
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
 
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
  input!{
    x: i32
  };
  let mut ans = 0;
  let mut rest = x;
  
  let q = rest / 500;
  ans += q * 1000;
  rest -= q * 500;
  
  let q = rest / 5;
  ans += q * 5;
  
  println!("{}", ans);
  
  
  
  
}

Measured memory_bytes: 4352
n = int(input())
# happy[i][j] : i日めにjをした。(j=0:a, j=1:b, j=2:c)
happy = [[0, 0, 0, 0] for i in range(n)]
for i in range(n):
    a,b,c = map(int, input().split())
    if i == 0:
        happy[0][0] = a
        happy[0][1] = b
        happy[0][2] = c
    else:
        happy[i][0] = max(happy[i-1][1], happy[i-1][2]) + a
        happy[i][1] = max(happy[i-1][0], happy[i-1][2]) + b
        happy[i][2] = max(happy[i-1][0], happy[i-1][1]) + c

print(max(happy[n-1][0], happy[n-1][1], happy[n-1][2]))


Measured memory_bytes: 60208
import sys

for line in sys.stdin:
    if line[0] == '#':
        break
    line = line.strip()
    step = [0, 0]
    before = int(line[0]) % 3 if int(line[0]) % 3 != 0 else 3
    NULL = 1000000
    for c in line[1:]:
        n = int(c) % 3 if int(c) % 3 != 0 else 3
        if n > before:
#            step[0], step[1] = step[1] + 1, step[0]
            step[0], step[1] = NULL, min(step[0], step[1] + 1)
        elif n < before:
            step[0], step[1] = min(step[0] + 1, step[1]), NULL
        else:
            step[0], step[1] = step[1], step[0]
        before = n
#        print step,
    print min(step)

Measured memory_bytes: 4576
//use proconio::{input, fastout};
use proconio::input;

//#[fastout]
fn main() {
    input! {
        h1: i32,
        m1: i32,
        h2: i32,
        m2: i32,
        k: i32,
    }
    let hm1 = h1 * 60 + m1;
    let hm2 = h2 * 60 + m2;
    
    println!("{}", hm2 - hm1 -k);
}


Measured memory_bytes: 2092
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define el '\n'
#define MOD 1000000007
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    string s;
    cin >> n >> s;
    int cnt = 0;
    for(int i = 0; i <= 999; i++){
        char a, b, c;
        if(i < 10){
            a = '0';
            b = '0';
            c = i + '0';
        } else if(i < 100){
            a = '0';
            b = (i / 10) + '0';
            c = (i % 10) + '0';
        } else {
            a = (i / 100) + '0';
            b = ((i / 10) % 10) + '0';
            c = (i % 10) + '0';
        }
        bool af = false, bf = false, cf = false;
            int ptr = -1;
            for(int j = 0; j < n; j++){
                if(s[j] == a){
                    af = true;
                    ptr = j;
                    break;
                }
            }
            for(int j = ptr + 1; j < n; j++){
                if(s[j] == b){
                    bf = true;
                    ptr = j;
                    break;
                }
            }
            for(int j = ptr + 1; j < n; j++){
                if(s[j] == c){
                    cf = true;
                    ptr = j;
                    break;
                }
            }
            if(af && bf && cf){
                cnt++;
            }
    }
    cout << cnt << '\n';
    return 0;
}

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

/************************** definations *******************************/
#define pi              2*acos(0.0)
#define ll              long long int
#define sc1(a)          scanf("%lld",&a)
#define sc2(a,b)        scanf("%lld %lld",&a,&b)
#define pf1(a)          printf("%lld\n",a)
#define pf2(a,b)        printf("%lld %lld\n",a,b)
#define Case(a)         printf("Case %d: ",a)
#define Casel(a)        printf("Case %lld: ",a)
#define INF             1e9
#define INFL            1e18
#define XX              first
#define YY              second
#define PB              push_back
#define MP              make_pair
#define NEWLINE         cout << endl;
#define DONE            cerr << "Done" << endl
#define PAUSE           system("pause")
#define DEBUG(x)        cerr << #x << " = " << x << endl
#define READ            freopen("alu.txt", "r", stdin)
#define WRITE           freopen("vorta.txt", "w", stdout)
#define FASTIO          ios_base::sync_with_stdio(false);cin.tie(NULL)
#define M               10000007
#define mod             100000007
/************************** definations *******************************/

int main()
{
    FASTIO;
    int n;
    cin>>n;
    vector<int> v;
    for(int i = 0;i<n;i++)
    {
        int x;
        cin>>x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    ll cnt = 0LL;
    for(int i = 0;i<n;i++) for(int j = i+1;j<n-1;j++)
    {
        int ind = upper_bound(v.begin(), v.end(), v[i]+v[j]-1) - v.begin()-1;
        cnt+= ind - j;
    }
    cout<<cnt;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD (long long)(1E9+7)
#define rep(i, n) for(int i = 0; i < n; i++)

using namespace std;

int main(){
	int a,b,c,x,y, tmp;
	cin >> a >> b >> c >> x >> y;
	int ans = a * x + b * y;	
    for(int i = 1; i <= max(x, y); i++) {
      //2iがABピザの枚数
     	tmp = 2 * i * c;
      	tmp += max(0, a * (x-i)) + max(0, b * (y - i));
		ans = min(ans, tmp);
    }
	cout << ans << endl;
}

Measured memory_bytes: 3560
//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
 /*int rem,n,i=0;
  cin>>n;
  while(n!=0)
  {
   rem =n%10;
    n=n/10;
    if(i==0)
    {
      int a=rem;
      i++;
    }
    else
    { 
      if(i==1)
      { int b=rem;
        i++;
      }
      else
        int c=rem;
    }
  }*/
  int a,b,c;
  cin>>a>>b>>c;
  if((a==b && b==c) || (a!=b && a!=c && b!=c))
    cout<<"No";
  else
    cout<<"Yes";
  return 0;
}


Measured memory_bytes: 256
n,k = map(int, input().split())
a = list(map(int, input().split()))
ans = 10**100
for i in range(n-k+1):
  st=a[i]
  en=a[i+k-1]
  if st*en<0:
    ans = min(ans, min(abs(st),abs(en))+abs(st-en))
  else:
    ans = min(ans, max(abs(st),abs(en)))
print(ans)

Measured memory_bytes: 14252
import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;
    private static final String YES = "Yes";
    private static final String NO = "No";

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

        int N = sc.nextInt();

        System.out.println(solve(N));
    }

    private static long solve(int N) {
        long count = 0;

        for (int i=1; i<=N; i++) {
            if (i%10 == 0) continue;
            if (i<10) {
                count += 1;
            } else if (i < 100) {
                if (i/10 == i%10) count += 3;
                else if (10 * (i%10) < i) {
                    count += 2;
                }
            } else if (i < 1000){
                if (i/100 == i%10) {
                    count += 1 + 1*2 + 1*2;
                    count += ((i%100)/10)*2;
                } else {
                    count += 1*2;
                    if (100*(i%10) < i) {
                        count += 10*2;
                    }
                }
            } else if (i < 10000) {
                if (i/1000 == i%10) {
                    count += 1 + 1*2 + 1*2 + 10*2;
                    count += ((i%1000)/10)*2;
                } else {
                    count += 1*2 + 10*2;
                    if (1000*(i%10) < i) {
                        count += 100*2;
                    }
                }
            } else if (i < 100000){
                if (i/10000 == i%10) {
                    count += 1 + 1*2 + 1*2 + 10*2 + 100*2;
                    count += ((i%10000)/10)*2;
                } else {
                    count += 1*2 + 10*2 + 100*2;
                    if (10000*(i%10) < i) {
                        count += 1000*2;
                    }
                }
            } else {
                if (i/100000 == i%10) {
                    count += 1 + 1*2 + 1*2 + 10*2 + 100*2 + 1000*2;
                    count += ((i%100000)/10)*2;
                } else {
                    count += 1*2 + 10*2 + 100*2 + 1000*2;
                    if (100000*(i%10) < i) {
                        count += 10000*2;
                    }
                }
            }
        }

        return count;
    }
}

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

A = [0]
B = [0]
for i in range(n):
    A.append(A[i]+a[i])
for i in range(m):
    B.append(B[i]+b[i])

cnt, j = 0, m#ここをfor文に入れなくていい。
for i, a_ in enumerate(A):
    d = k-a_
    t = 0
    if d < 0:
        break
    while d < B[j]:
        j-=1
    t = i+j
    cnt = max(cnt, t)
print(cnt)

Measured memory_bytes: 127132
/*~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=
    WRITER:kakitamasziru/OxOmisosiru
~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=*/
#define _GLIBCXX_DEBUG
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#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 <iomanip>
#include <limits>//setprecision
//#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <math.h>//pow,,,
#include <cmath>//abs,,,
//#include <unordered_map> // unordered_map
//#include <unordered_set> // unordered_set
#include <bitset> // bitset
//#include <cctype> // isupper, islower, isdigit, toupper, tolower
//It is so troublesome that I include bits/stdc++.h !
using namespace std;

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; }
const long long INF = 100100100100100;
const int MOD = 1000000007;
typedef pair<int,int> P;
//NのM乗を求める(繰り返し二乗法)
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //最下位ビット(*N)が1の時は単独でNをかける
    if (M & 1) res = (res * N) % MOD;

    return res %= MOD;
}

vector<int> retu(100001);

int ok(int key,int index){
    if(retu.at(index) > key) return 1;
    else if(retu.at(index) < key) return 2;
    else if(retu.at(index) == key) return 3;
}

bool binary_search(int key,int size){
    //left,right,midはいずれもindex
    int left = -1,right = size;
    while(right - left > 1){
        int mid = left + (right-left)/2;
        int hantei = ok(key,mid);
        if(hantei == 1) right = mid;
        else if(hantei == 2) left = mid;
        else if(hantei == 3) return true;
    }
    if(retu.at(right) == key) return true;
    else return false;
}

int main() {
    int N;cin >> N;
    for(int i = 0;i<N;i++) cin >> retu.at(i);
    int Q;cin >> Q;
    vector<int> query(Q);
    for(int i = 0;i<Q;i++) cin >> query.at(i);
    int ans = 0;
    for(int i = 0;i<Q;i++){
        bool count = binary_search(query.at(i),N);
        if(count) ans++;
    }
    cout << ans << endl;
    

    // PLEASE GIVE ME THE "ACCEPTED" !
}


Measured memory_bytes: 3280
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

constexpr int atcoder_mod = 1e9+7;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	int a=in(),b=in(),C=in();
	double pi = 4.0*atan(1.0);
	double S = 0.5*a*b*sin(C*pi/180.0);
	double L = a+b+sqrt(a*a+b*b-2*a*b*cos(C*pi/180.0));
	double H = b*sin(C*pi/180.0);
	printf("%.10lf\n%.10lf\n%.10lf\n",S,L,H);
		
	return 0;
}



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

int A[100007];
int dp[100007];
int main(){
  int n,k;
  cin >> n >> k;
  memset(dp,0,sizeof(dp));
  for(int i=0;i<n;i++) cin >> A[i];
  for(int i=0;i<k;i++){
    if(i==0){
      dp[i]=0;
    }
    else{
      dp[i] = abs(A[i]-A[0]);
    }
  }
  for(int i=k;i<n;i++){
    dp[i]=INT_MAX;
    for(int j=i-k;j<i;j++){
      dp[i] = min(dp[i],abs(A[i]-A[j])+dp[j]);
    }
  }
  cout<<dp[n-1]<<endl;
}


Measured memory_bytes: 1024
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n, k int
	fmt.Scanf("%d %d", &n, &k)

	a := make([]int, n)

	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
	}

	fmt.Println(logic(a, k))
}

func logic(nums []int, k int) int {
	dic := makeDicionary(nums)
	sort.Sort(dic)

	if dic.Len() <= k {
		return 0
	}

	sum := 0

	for i := 0; i < dic.Len()-k; i++ {
		sum += dic[i].Value
	}
	return sum
}

func makeDicionary(nums []int) Dictionary {
	m := make(map[int]int)
	for _, num := range nums {
		m[num]++
	}

	i := 0
	dic := make(Dictionary, len(m))
	for k, v := range m {
		dic[i] = kv{Key: k, Value: v}
		i++
	}

	return dic
}

type kv struct {
	Key   int
	Value int
}

type Dictionary []kv

func (d Dictionary) Len() int {
	return len(d)
}

func (d Dictionary) Less(i, j int) bool {
	return d[i].Value < d[j].Value
}

func (d Dictionary) Swap(i, j int) {
	d[i], d[j] = d[j], d[i]
}


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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a) accumulate(all(a), 0LL)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



signed main(){
    string s;
    cin >> s;
    string ans;
    if(s == "ABC") ans = "ARC";
    else ans = "ABC";
    cout << ans << endl;
    return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef complex<double> P;

#define pb push_back
#define pf push_front
#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end()) // ユニークなvectorにする。連続した値を除去して切り出す。
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)
#define ADD(a, b) a = (a + b) % mod
#define MUL(a, b) a = (a * b) % mod
#define int ll
#define INF 100000000

#define POS(x) cout<<((x)?"POSSIBLE":"IMPOSSIBLE")<<endl;
#define Pos(x) cout<<((x)?"Possible":"Impossible")<<endl;
#define YES(x) cout<<((x)?"YES":"NO")<<endl;
#define Yes(x) cout<<((x)?"Yes":"No")<<endl;
#define yes(x) cout<<((x)?"yes":"no")<<endl;

__attribute__((constructor))
void initial() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

int n;
vector<string> ss;

bool find(string s){
    for (int i = 0; i < ss.size(); ++i) {
        if(ss[i] == s) return true;
    }
    return false;
}

bool check(string s){

    if(ss.empty()) {
        ss.pb(s);
        return false;
    }

    string before = ss.back();
    char last = before.back();

    if(last != s.front()) return true;

    if(find(s)) return true;

    ss.pb(s);

    return false;
}

signed main() {
    vector<string> vs;

    cin >> n;

    rep(i,n){
        string s;
        cin >> s;
        vs.pb(s);
    }

    rep(i,n){
        string s = vs[i];
        if(check(s)) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <tuple>

template <class T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

using lint = long long;
constexpr lint INF = 1LL << 50;

struct Edge {
    int dst;
    lint cost;
    explicit Edge(int dst, lint cost) : dst(dst), cost(cost) {}
};

using Graph = std::vector<std::vector<Edge>>;

std::vector<lint> dijkstra(const Graph& graph, int r) {
    std::vector<lint> dist(graph.size(), INF);
    dist[r] = 0;
    MinHeap<std::pair<lint, int>> que;
    que.emplace(dist[r], r);

    while (!que.empty()) {
        lint d;
        int v;
        std::tie(d, v) = que.top();
        que.pop();
        if (dist[v] < d) continue;

        for (auto e : graph[v]) {
            int u = e.dst;
            lint nd = d + e.cost;
            if (dist[u] > nd) {
                dist[u] = nd;
                que.emplace(nd, u);
            }
        }
    }

    return dist;
}

void solve() {
    int n, m, s, t, a, b;
    std::cin >> n >> m >> s >> t >> a >> b;
    --s, --t, --a, --b;

    Graph graph(n);
    while (m--) {
        int u, v;
        lint c;
        std::cin >> u >> v >> c;
        --u, --v;
        graph[u].emplace_back(v, c);
        graph[v].emplace_back(u, c);
    }

    auto ds = dijkstra(graph, s),
         da = dijkstra(graph, a),
         db = dijkstra(graph, b);

    std::vector<int> vs(n);
    std::iota(vs.begin(), vs.end(), 0);
    std::sort(vs.begin(), vs.end(),
              [&](int u, int v) { return ds[u] < ds[v]; });

    std::vector<std::vector<lint>>
        dist(3, std::vector<lint>(n, INF));

    for (auto v : vs) {
        dist[0][v] = da[v];
        dist[1][v] = db[v];
        dist[2][v] = da[v] + db[v];

        for (auto e : graph[v]) {
            int u = e.dst;
            if (ds[u] + e.cost > ds[v]) continue;
            for (int k = 0; k < 3; ++k) {
                dist[k][v] = std::min(dist[k][v], dist[k][u]);
            }
        }

        dist[2][v] = std::min({dist[2][v],
                               dist[0][v] + db[v],
                               dist[1][v] + da[v]});
    }

    std::cout << std::min(da[b], dist[2][t]) << std::endl;
}

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

    solve();

    return 0;
}



Measured memory_bytes: 21392
N = int(input())
a = input().split()
for l in range(N):
    a[l] = int(a[l])
for i in range(N):
  if i < N-1:
    if a[N-i-1] >= a[N-i-2]:
      continue
    elif a[N-i-1] + 1 == a[N-i-2]:
      a[N-i-2] -= 1
    else:
      print('No')
      break
  else:
    print('Yes')

Measured memory_bytes: 11152
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

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

    void solve(Scanner sc) {
        int n = sc.nextInt();
        int[] aList = new int[n];
        long asum = 0;
        for (int i = 0; i < n; i++) {
            aList[i] = sc.nextInt();
            asum += aList[i];
        }

        long bsum = 0;
        long ans = 0;
        long a= 0;
        for (int i = 0; i < n; i++) {
            int b = sc.nextInt();
            aList[i] -= b;
            bsum += b;

            if (aList[i] < 0) {
                ans++;
                a += -(aList[i]);
            }
        }

        if (bsum > asum) {
            System.out.println(-1);
            return;
        }

        Arrays.sort(aList);
        long b = 0;
        for (int i = aList.length - 1; i >= 0; i--) {
            if (b >= a) {
                break;
            }

            b += aList[i];
            ans++;
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 64632
#define _CRT_SECURE_NO_WARNINGS
#include <cassert>
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <climits>
using namespace std;

#define int long long
#define pii pair<int, int>
#define ld long double

#define form(i, n) for (int i = 0; i < (n); ++i)
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford(i, n) for (int i = (n-1); i >= 0; --i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)

#define chmax(x, v) x = max(x, (v));
#define chmin(x, v) x = min(x, (v));

void solve();
signed main()
{
#ifdef LOCAL_HUGO
	freopen("in.txt", "r", stdin);
	int t; cin >> t;
	form(i,t) { solve(); cout << "###\n"; }
#else
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
#endif
}

void solve()
{
	int a, b, c;
	cin >> a >> b >> c;
	int ans = 0;
	if (b >= c) { ans = b + c; } 
	else {
		ans += 2 * b;
		c -= b;
		ans += min(a+1, c);
	}
	cout << ans << '\n';
}

Measured memory_bytes: 256
from sys import stdin, setrecursionlimit
#input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

N = int(input())
#N, M = map(int, input().split())
#A = list(map(int, input().split()))
#A = [int(input()) for _ in range(N)]
#ABC = [list(map(int, input().split())) for _ in range(N)]
#S = input()
#S = [input() for _ in range(N)]

answer = 0
rest = 0
for i in range(2 * 10 ** 6):
    rest *= 10
    rest += 7
    rest %= N
    answer += 1
    if rest == 0:
        print(answer)
        exit()
print(-1)    

Measured memory_bytes: 67948
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

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

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

# 掃き出し法
# ex: [[1,1,0],[1,0,1],[1,1,1]] -> [[1,1,0],[0,1,1],[0,0,1]]
# 行ごとの二進数値で入力する．上の例だと A = [6,5,7] -> g = [6,3,1]
def F2_row_reduction(A):
    n = len(A)
    g = A[:]
    rank = 0
    max_digit = len(format(max(A),'b'))
    for col in range(max_digit)[::-1]:
        pivot = -1
        for row in range(rank,n):
            if g[row]>>col & 1:
                pivot = row
                break
        if pivot == -1: 
            continue
        g[pivot],g[rank] = g[rank],g[pivot]
        for row in range(rank+1,n):
            if g[row]>>col & 1:
                g[row] ^= g[rank]
        rank += 1
    return g

T = I()
ans = []
for i in range(T):
    N = I()
    A = LI()
    S = list(input())
    d = []
    flag = False
    for j in range(N)[::-1]:
        rank = 0
        if S[j] == '0':
            d.append(A[j])
            d = F2_row_reduction(d)
            if d[-1] == 0:
                d.pop()
            else:
                rank += 1
        else:
            d.append(A[j])
            d = F2_row_reduction(d)
            if d[-1] == 0:
                d.pop()
            else:
                flag = True
                ans.append(1)
                break
    if not flag:
        ans.append(0)

for a in ans:
    print(a)

Measured memory_bytes: 69724
#include<bits/stdc++.h>
using namespace         std;
#define                 int long long
#define                 pb push_back
#define                 mp make_pair
#define st(arr,a)       memset(arr,a,sizeof arr)
#define                 nl cout<<endl
#define                 real signed
#define                 endl '\n'              
#define bitcount(x)     __builtin_popcountll(x)
const int MOD = 1000000007ll;
#define forn(i,a,b)     for(int i=a;i<=b;i++)
#define rfor(i,a,b)     for(int i=a;i>=b;i--)
#define all(x)          x.begin() , x.end()
#define pi pair<int,int>
#define X first
#define Y second
#define N 314159

int n,m;
int arr[31];

signed main() 
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
     cin>>n>>m;
     forn(i,1,n)
     {
         int k;cin>>k;
         forn(i,1,k)
         {
             int a;
             cin>>a;
             arr[a]++;
         }
     }
     int ans=0;
     forn(i,1,m)
     ans+=arr[i]==n;
     cout<<ans;
     
     
    



     return 0;

}

//       g++ -g c.cpp ; ./a.exe

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <queue>
#include <iomanip>
#include <set>
//#include <bits/stdc++.h>
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(a>b){a=b;return true;}return false;}
using namespace std;
#define ALL(X) X.begin(),X.end()
using ll = long long int;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
const int MOD=1000000007;//1e9+7
//const int MOD=998244353;
const int INTMAX=2147483647;//2e9
const ll LLMAX=9223372036854775807;//9e17


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll N,K;
    cin>>N>>K;
    vll A(N);
    for(ll i=0;i<N;i++)cin>>A[i];
    for(ll k=0;k<K;k++){
        vll B(N,0);
        for(ll i=0;i<N;i++){
            if(i-A[i]>=0)B[i-A[i]]++;
            else B[0]++;
            if(i+A[i]+1<N)B[i+A[i]+1]--;
        }
        for(ll i=1;i<N;i++){
            B[i]+=B[i-1];
        }
        A=B;
        bool ok=true;
        for(ll i=0;i<N;i++){
            if(A[i]!=N){
                ok=false;
                break;
            }
        }
        if(ok)break;
    }
    for(ll i=0;i<N;i++)cout<<A[i]<<" ";
    cout<<endl;
    
    return 0;
}


Measured memory_bytes: 6344
#ARc081C
import sys

n=int(raw_input())
l=map(int,raw_input().split())
l1=sorted(l,reverse=True)
l2=[]
for i in xrange(n-1):
 if l1[i]==l1[i+1]:
  l2.append(l1[i])
if l2==[]:
 print 0
 sys.exit()
ls=sorted(list(set(l2)),reverse=True)
if l1.count(ls[0])>3:
 res=ls[0]**2
else:
 res=ls[0]*ls[1]
print res


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

#define FOR(i, j, k) for (int i = j; i < k; i++)
#define REP(i, j) FOR(i, 0, j)
#define RFOR(i, k, j) for (int i = k - 1; i >= j; i--)
#define RREP(i, j) RFOR(i, j, 0)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<pii> vpii;

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

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

template <typename T> istream &operator>>(istream &is, vector<T> &vec) {
  for (T &x : vec)
    is >> x;
  return is;
}

int main() {

  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout << fixed;

  int n;
  cin >> n;

  REP(i, n - 1) {
    FOR(j, i + 1, n) {
      int x = abs(i - j);
      REP(k, 10) if (x & (1 << k)) {cout << k + 1 << " "; break;}
    }
    cout << endl;
  }

  return 0;
}


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

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

  int count = 1;
  char now = S.at(0);

  for(int i=1; i<S.size(); i++){

    count++;
    
    if(now == S.at(i)){
      i++;
      now = NULL;
      if(i == S.size()){
        count--;
        break;
      }
    }else{
      now = S.at(i);
    }

  }
  cout << count << endl;
}

Measured memory_bytes: 640
#include <iostream>
//#include <iomanip>
//#include <string>
//#include <vector>
//#include <algorithm>
//#include <utility>
//#include <set>
//#include <map>
//#include <queue>
//#include <bitset>
//#include <math.h>
using namespace std ;
using ll = long long ;
//using ld = long double ;
//using vll = vector<ll> ;
//using vvll = vector<vll> ;
//using vc = vector<char> ;
//using vvc = vector<vc> ;
//using vb = vector<bool> ;
//using vvb = vector<vb> ;
//using pll = pair<ll,ll> ;

//ll mod = 1000000007 ;
//long double pie = acos(-1) ;

//string yorn(bool a){if(a) return"Yes" ; return "No" ;}
//string YorN(bool a){if(a) return"YES" ; return "NO" ;}
//ll gcd(long long a,long long b){if(b==0) return a ; return gcd(b,a%b) ;}
//ll lcm(long long a,long long b){return a/gcd(a,b)*b ;}
//ll sa(long long a,long long b){if(a>b) return a-b ; return b-a ;}
//void mysort(vector<long long> &a){sort(a.begin(),a.end()) ;}
//void myrev(vector<long long> &a){reverse(a.begin(),a.end()) ;}

int main(){
	ll a,b,c,k ;
	cin >> a >> b >> c >> k ;
	if(k&1) cout << b-a << endl ;
	else cout << a-b << endl ;
}


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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

int64_t gcd(int64_t a,int64_t b){
	if(b==0) return a;
	return gcd(b,a%b);
}

int64_t lcm(int64_t a,int64_t b){
	return a/gcd(a,b)*b;
}

void solve(int n){
    map<int,vector<int>> x;
    rep(i,0,n){
        int d,t;
        cin >> d >> t;
        if(x.find(d)==x.end()) x[d].resize(d);
        rep(j,0,d){
            int a;
            cin >> a;
            x[d][(j-t+d)%d]+=a;
        }
    }

    for(;;){
        bool update=false;
        for(auto &p:x){
            for(auto &q:x){
                const int a=p.first,b=q.first;
                if(a==b) continue;
                const int c=lcm(a,b),d=gcd(a,b);
                if(d==1) continue;
                vector<int> v=x[c];
                if(v.empty()) v.resize(c);
                rep(i,0,c) v[i]+=p.second[i%a]+q.second[i%b];
                if(a==c) rep(i,0,c) v[i]-=p.second[i];
                if(b==c) rep(i,0,c) v[i]-=q.second[i];
                x.erase(a);
                x.erase(b);
                x[c]=v;

                update=true;
                break;
            }
            if(update) break;
        }
        if(!update) break;
    }

    int ans=0;
    for(auto &p:x){
        int ma=0;
        for(int a:p.second) ma=max(ma,a);
        ans+=ma;
    }
    cout << ans << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(10);
    for(;;){
        int n;
        cin >> n;
        if(!n) break;
        solve(n);
    }
    return 0;
}

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

int main(){
    int n,c;
    cin >> n >> c;
    
    n++;
    int cake(0);
    for(int i=0;i<c;i++){
        int x;  cin >> x;
        cake += x;
    }

    if(cake%n==0){
        cout << cake/n << endl;
    }else{
        cout << cake/n+1 << endl;
    }

    return 0;
}


Measured memory_bytes: 3108
s = input()

ans = 0
b = ""

i = 0
while i < len(s):
    if (len(b)==1 and s[i]==b) or (i==len(s)-2 and s[i]==s[i+1]):
        b = s[i:i+2]
    else:
        b = s[i]
    ans += 1
    #print(i,b)
    i += len(b)

print(ans)

Measured memory_bytes: 3500
#include<bits/stdc++.h>
using namespace std;
using p=pair<int,int>;
#define int long long
#define rep(i,N) for(int i=0;i<N;i++)

signed main(){
  int X,A,B;
  cin>>X>>A>>B;
  if(abs(A-X)>=abs(B-X))cout<<"B"<<endl;
  else cout<<"A"<<endl;
  return 0;
} 

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int a,b; char c; cin>>a>>c>>a>>b;
	cout<<(a*100+b>430?"TBD"s:"Heisei"s)<<"\n"s;
}

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


int main(){
	int a,b,c;
	cin >> a >> b >> c;
	set<int> s;
	
	for(int i=0;i<c;++i){
		int tmp = a+i;
		if(a<= tmp && tmp <= b) s.insert(tmp);
		tmp = b-i;
		if(a<= tmp && tmp <= b) s.insert(tmp);
	}
	
	//sort(s.begin(),s.end());
	
	set<int>::iterator it = s.begin();
	while(it != s.end()){
		cout << *it << endl;
		it++;
	}
	
	
	
	return 0;
	
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x,i##end=y;i<=i##end;++i)
#define _rep(i,x,y) for(int i=x,i##end=y;i>=i##end;--i)
#define N 200005
int a[N],b[N],n;
int x,y;
std::vector<int> p,q;
int main(){
	std::ios::sync_with_stdio(0);
	std::cin.tie(0),std::cout.tie(0);
	std::cin>>n;
	rep(i,1,n) std::cin>>a[i],b[i]=a[i];
	std::sort(b+1,b+n+1);
	x=b[n>>1],y=b[(n>>1)+1];
	/*rep(i,1,n){
		if(x==a[i]) p.push_back(i);
		if(y==a[i]) q.push_back(i);
	}*/
	rep(i,1,n){
		if(a[i]>=y) std::cout<<x<<'\n';
		else std::cout<<y<<'\n';
	}
	return 0;
}

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

typedef long long llint;

string s, t;

int main() {
    cin >> s >> t;
    string ans = "No";
    for (int i = 0; i < t.length(); i++) {
        if (s == t) {
            ans = "Yes";
            break;
        }
        s += s[0];
        s.erase(s.begin());
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll a7=1000000007;
ll inf=1000000000000000;
#define rep(i,l,r) for(ll i=l;i<=r;i++)

ll min(ll a,ll b){
    if(a<b)return a;
    return b;
}
ll max(ll a,ll b){
    if(a>b)return a;
    return b;
}

ll a[2][100010];

int main(){
    ll n;cin>>n;
    vector<pair<ll,ll>> c;
    ll ans=0;
    rep(i,0,n-1){
        rep(j,0,1){
            cin>>a[j][i];
        }
        c.push_back(make_pair(a[0][i]+a[1][i],i));
        ans=ans-a[1][i];
    }
    sort(c.begin(),c.end());
    for(ll i=n-1;i>=0;i--){
        if(((n-1)-i)%2==0){
            ans+=c[i].first;
        }
    }
    cout<<ans<<endl;
    
    return 0;
}


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

ll mod=10000;

ll dp[111][5][5];
int a[111];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,k; cin >> n >> k;
	for(int i=0;i<k;i++){
		int x,y; cin >> x >> y;
		a[x]=y;
	}
	dp[0][3][3]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<4;j++){
			for(int p=0;p<4;p++){
				if(dp[i][j][p]==0)continue;
				if(a[i+1]!=0){
					if(a[i+1]==j+1&&a[i+1]==p+1)continue;
					if(1){
						(dp[i+1][a[i+1]-1][j]+=dp[i][j][p])%=mod;
					}
				}
				else{
					if(j==p){
						for(int h=0;h<3;h++){
							if(p==h)continue;
							(dp[i+1][h][j]+=dp[i][j][p])%=mod;
						}
					}
					else{
						for(int h=0;h<3;h++){
							(dp[i+1][h][j]+=dp[i][j][p])%=mod;
						}
					}
				}
			}
		}
	}
	ll ans=0;
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			//cout << i << " " << j << " " << dp[n-1][i][j] << endl;
			ans+=dp[n][i][j];
		}
	}
	cout << ans%mod << endl;
}


Measured memory_bytes: 3156
import heapq
N, K = map(int, input().split())
A = list(map(int, input().split()))

knot = []
for i in range(N - 1):
    heapq.heappush(knot, (-A[i]-A[i+1], i))

ans = []
seen = [False]*N
while knot:
    L, i = heapq.heappop(knot)
    L = -L

    if seen[i]:
        continue
    if L < K:
        break

    seen[i] = True
    ans.append(i + 1)

    if i + 1 < N - 1:
        heapq.heappush(knot, (-L - A[i + 1], i + 1))
    if i - 1 >= 0:
        heapq.heappush(knot, (-L - A[i - 1], i - 1))

if len(ans) != N - 1:
    print("Impossible")
else:
    print("Possible")
    print(*ans[::-1], sep="\n")


Measured memory_bytes: 32472