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

using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

/* [💭] [💡] [🎈] */

const ll mod = 1'000'000'007;
ll pow2[200001];

pll rev(const pll &p) {
    return (p.second < 0 ? pll(-p.second, p.first) : pll(p.second, -p.first));
}

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

    pow2[0] = 1;
    for (int i = 1; i <= 200000; i++) {
        pow2[i] = pow2[i - 1] << 1;
        pow2[i] %= mod;
    }

    ll n;
    cin >> n;

    int zc = 0;
    map<pll, int> mp, revmp;
    for (int i = 0; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        if (!a && !b) {
            zc++;
            continue;
        }
        if (!a) {
            mp[pll(0, -1)]++;
            continue;
        }
        if (!b) {
            mp[pll(1, 0)]++;
            continue;
        }
        if (a < 0) a *= -1, b *= -1;
        ll g = abs(__gcd(a, b));
        a /= g, b /= g;
        mp[pll(a, b)]++;
    }
    for (const auto &kv: mp) revmp[rev(kv.first)] += mp[kv.first];

    ll p = 1;

    map<pll, bool> visit;
    for (const auto &kv: mp) {
        if (visit[kv.first]) continue;
        visit[kv.first] = true;
        visit[rev(kv.first)] = true;

        if (revmp.find(kv.first) != revmp.end()) {
            p *= (pow2[kv.second] + pow2[revmp[kv.first]] + mod - 1) % mod;
        } else {
            p *= pow2[kv.second];
        }
        p %= mod;
    }

    p += zc;

    cout << (p + mod - 1) % mod;

    return 0;
}

Measured memory_bytes: 55180
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
long long inf=(long long)1E17;
#define i_7 (long long)(1E9+7)
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
using namespace std;
long long gcd(long long a, long long b){
  if(a<b){
    swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd(b,a%b);
  }
}
 
long long lcm(long long x, long long y){
  return (x/gcd(x,y))*y;
}
 
class UnionFind {
    public:
    //各頂点の親の番号を格納する。その頂点自身が親だった場合は-(その集合のサイズ)を入れる。
    vector<int> Parent;
    
    //クラスを作るときは、Parentの値を全て-1にする。
    //以下のようにすると全てバラバラの頂点として解釈できる。
    UnionFind(int N) {
        Parent = vector<int>(N, -1);
    }
    
    //Aがどのグループに属しているか調べる
    int root(int A) {
        if (Parent[A] < 0) return A;
        return Parent[A] = root(Parent[A]);
    }
    
    //自分のいるグループの頂点数を調べる
    int size(int A) {
        return -Parent[root(A)];//先祖をrootで取っておきたい。
    }
    
    //AとBをくっ付ける
    bool connect(int A, int B) {
        //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
        A = root(A);
        B = root(B);
        if (A == B) {
            //すでにくっついてるからくっ付けない
            return false;
        }
        
        //大きい方(A)に小さいほう(B)をくっ付けたい
        //大小が逆だったらAとBをひっくり返す。
        if (size(A) < size(B)) swap(A, B);
        
        //Aのサイズを更新する
        Parent[A] += Parent[B];
        //Bの親をAに変更する
        Parent[B] = A;
        
        return true;
    }
};
 
int main(){
  string s;
  cin>>s;
  int a,z;
  REP(i,s.size()){
    if(s[i]=='A'){
      a = i;
      break;
    }
  }
  REP(i,s.size()){
    if(s[s.size()-i-1]=='Z'){
      z = s.size()-i-1;
      break;
    }
  }
  cout<<z-a+1<<endl;
  return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>
int main()
{
    int s,t;
    char a[200],b[200],c[200];
    scanf("%s %s",a,b);
    scanf("%d %d",&s,&t);
    scanf("%s",c);
    if(strcmp(a,c)==0){s=s-1;}
    else if(strcmp(b,c)==0){t=t-1;}
    printf("%d %d",s,t);
    return 0;
}


Measured memory_bytes: 128
import heapq
n,m = map(int,input().split())
al = [[] for i in range(10**5)]
ans = 0
h = []
for i in range(n):
    a,b = map(int,input().split())
    al[a-1] += [-b]
for i in range(m):
    for j in al[i]:
        heapq.heappush(h,j)
    if h:
        ans -= heapq.heappop(h)
print(ans)

Measured memory_bytes: 87752
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    
    vector<long long int> a(N);
    vector<long long int> asum(N+1, 0);
    for(int n=0; n<N; n++) {
        cin >> a[n];

        asum[n+1] = asum[n]+a[n];
    }
    
    long long int ans=1e16;
    for(int n=0; n<N-1; n++) {
        long long int tmp=abs(asum[n+1]-asum[0]-(asum[N]-asum[n+1]));
        ans = min(ans, tmp);
    }
    
    cout << ans << endl;

    return 0;
    
}

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

using namespace std;

using ll = long long;

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

  cin >> N >> A >> B;

  ll k = N / (A + B);
  ll r = N % (A + B);

  ll ans = k * A + min(r, A);
  cout << ans << endl;

  return 0;
}


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

MOD = 1000000007

d = {}
for c in S:
    if c in d:
        d[c] += 1
    else:
        d[c] = 1

result = 1
for x in d.values():
    result *= x + 1
    result %= MOD
result += MOD - 1
result %= MOD

print(result)


Measured memory_bytes: 3188
S = input()
N = len(S)
MOD = 1000000007
dp = [[0]*4 for i in range(N+1)]
for i in range(N, -1, -1):
    for j in range(3, -1, -1):
        if i == N:
            dp[i][j] = 1 if j == 3 else 0
        else:
            dp[i][j] = dp[i+1][j] * (3 if S[i] == '?' else 1)
            if j < 3 and (S[i] == '?' or S[i] == "ABC"[j]):
                dp[i][j] += dp[i+1][j+1]
            dp[i][j] %= MOD
print(dp[0][0])

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

int main(){
	const unsigned int INF = 1 << 31;
	unsigned int dp[101][101], a[101], b[101];
	int n;
	// dp[i][j] := 山 i..j をひとつにまとめるのにかかるコスト
	// 初期化
	for(int i=0 ; i < 101 ; i++ ){
		for(int j=0 ; j < 101 ; j++ ){
			dp[i][j] = (i == j)? 0 : INF ;
		}
	}
	
	cin >> n;
	for(int i=0 ; i < n ; i++ ){
		cin >> a[i] >> b[i];
	}
	for(int k = 1 ; k < n ; k++ ){
		for(int i = 0 ; i+k < n ; i++ ){
			for(int j = i ; j < i+k ; j++ ){
				// cost := i..j と j+1..i+k をまとめるときにかかるコスト
				unsigned int cost = a[i] * b[j] * a[j+1] * b[i+k];
				dp[i][i+k] = min( dp[i][i+k] , dp[i][j] + dp[j+1][i+k] + cost );
			}
		}
	}
	cout << dp[0][n-1] << endl;
}

Measured memory_bytes: 1196
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define REPR(i,n) for(ll i=n-1;i>=0;i--)

typedef long long ll;
#define INF 1e18

int main(){
	ll n; cin>>n;
	n%=10;
	if(n==3){
		cout<<"bon"<<endl;
	}else if(n==2 || n==4 || n==5 || n==7 || n==9 ){
		cout<<"hon"<<endl;
	}else{
		cout<<"pon"<<endl;
	}
	return 0;
}

Measured memory_bytes: 3552
#include <stdio.h>
#include <math.h>
int Dudney_Number(int a, int n, int m)
{
	int y, cnt = 0, dig_sum, x, tmp;
	for (y = 1; y <= 72; y++)//99999999⇒72とする
	{
		x = pow((y + a), n);
		dig_sum = 0;
		tmp = x;
		while (tmp > 0)
		{
			dig_sum += tmp % 10;//一の位の数を合算
			tmp /= 10;//右に1ビットシフト
		}

		if ((x <= m) && (dig_sum == y))//デュードニー数の条件
		{
			cnt++;
		}
	}
	return cnt;
}

int main()
{
	int a, n, m, Ans;

	scanf("%d%d%d", &a, &n, &m);
	Ans = Dudney_Number(a, n, m);
	printf("%d\n", Ans);

	return 0;
}



Measured memory_bytes: 2104
#include <stdio.h>

int main(void)
{
  int inh,outh,inm,outm,ins,outs,ansh,ansm,anss,i,j,k;

  for(i=0;i<3;i++){
    ansh=0;
    ansm=0;
    anss=0;

    scanf("%d %d %d", &inh, &inm, &ins);
    scanf("%d %d %d", &outh, &outm, &outs);

    ansh=outh-inh;

    if(inm<=outm){
      ansm=outm-inm;
    } else if(inm>outm){
      ansm=60-inm+outm;
      ansh--;
    }

    if(ins<=outs){
      anss=outs-ins;
    } else if(ins>outs&&ansm!=0){
      anss=60-ins+outs;
      ansm--;
    } else if(ins>outs&&ansm==0){
      anss=60-ins+outs;
      ansm=59;
      ansh--;
    }

    printf("%d %d %d\n", ansh, ansm, anss);
  }

  return 0;
}


Measured memory_bytes: 600
#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int x, y; cin >> x >> y;
    int s = 0;
    for(int i = 0; i < x-y; i++) s += 100;
    for(int i = 0; i < y; i++) s += 1900;
    cout << s * pow(2, y);
}

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

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

	int n, k;
	cin >> n >> k;
	int ans = 0;
	while(true) {
		if(n <= 0) {
			break;
		} 
		n = n / k;
		ans++;
	}
	cout << ans << endl;
}

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

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

int main(){
    int h, w;
    cin >> h >> w;
    int cnt = 0;
    rep(i, h){
        rep(j, w){
            char a;
            cin >> a;
            if(a == '#') cnt++;
        }
    }
    if(cnt == (h + w - 1)) cout << "Possible" << endl;
    else cout << "Impossible" << endl;
    return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define rep(i,n) FOR(i,0,n)
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define vint vector<int>
#define vdouble vector<double>
#define vstring vector<string>
using namespace std;

#include<map>
#include<set>
#include<queue>

typedef long long ll;
typedef unsigned long long ull;

const int MAX_N = 1000000;

int N;
int A[300000];

int main() {
    cin >> N;
    rep(i, N*3){ cin >> A[i]; }
    sort(&A[0], &A[N*3]);

    ll ret = 0;
    int i = N*3-2;
    int c = N;
    while(c > 0){
        ret += A[i];
        i -= 2;
        c--;
    }

	cout << ret << endl;
}

Measured memory_bytes: 1536
S = input() + "_"
i = 0
d = 0
ans = 0
for k in range(len(S)):
    if S[k] == "<":
        i += 1
    elif S[k] == ">":
        d += 1
    if S[k] == ">" and S[k+1] == "<":
        m = min(i,d)
        M = max(i,d)
        ans += M*(M+1)//2 + m*(m-1)//2
        i = 0
        d = 0
m = min(i,d)
M = max(i,d)
ans += M*(M+1)//2 + m*(m-1)//2
print(ans)


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

int main(){
  int n;
  string s;
  cin >> n >> s;
  
  int ans=1;
  for(int i=0;i<n-1;i++){
    if(s.at(i)!=s.at(i+1)){
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<vector>
using namespace std;

#define MAX_N 22
#define MAX_C 222222
#define INF 9999999999.99

vector<int>yakusuu[MAX_C];
double dp[MAX_N][MAX_C];
int n;
int x[MAX_N];

void yaku() {
	for (int i = 1; i < MAX_C; i++) {
		for (int j = i; j < MAX_C; j += i) {
			yakusuu[j].push_back(i);
		}
	}
}

int main() {
	yaku();
	cin >> n;
	x[0] = 1;
	for (int i = 1; i <= n; i++) {
		cin >> x[i];
	}
	dp[0][0] = INF;
	for (int i = 1; i < MAX_C; i++) {
		dp[1][i] = 1.0*abs(x[1] - i) / x[1];
	}
	for (int i = 2; i < MAX_N; i++) {
		for (int j = 0; j < MAX_C; j++) {
			dp[i][j] = INF;
		}
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j < MAX_C; j++) {
			for (int k = 0; k < yakusuu[j].size(); k++) {
				double pos1 = dp[i - 1][yakusuu[j][k]];
				double pos2 = 1.0*abs(x[i] - j) / x[i];
				double pos3 = max(pos1, pos2);
				dp[i][j] = min(dp[i][j], pos3);
			}
		}
	}
	double minx = INF;
	for (int i = 0; i < MAX_C; i++) {
		minx = min(minx, dp[n][i]);
	}
	cout << fixed << setprecision(15) << minx << endl;
	return 0;
}

Measured memory_bytes: 61612
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();  // input Integer
    int a = sc.nextInt();  // input Integer
    String s = sc.next();  // input String
    System.out.println(s.substring(0,a-1)+s.substring(a-1,a).toLowerCase()+s.substring(a));
  }
}


Measured memory_bytes: 21844
#include<cstdio>
#include<cmath>
using namespace std;

int n, m, k;

double rec(int cnt, int sum){
	if(cnt == n){
		if(sum - k < 1) return 1.0 / pow((double)m, (double)n);
		return (double)(sum - k) / pow((double)m, (double)n);
	}
	double ret = 0.0;
	for(int i = 1; i <= m; i++) ret += rec(cnt + 1, sum + i);
	return ret;
}

int main(){
	for(;;){
		scanf("%d %d %d", &n, &m, &k);
		if(n == 0 && m == 0 && k == 0) break;
		printf("%.10lf\n", rec(0, 0));
	}
	return 0;
}


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

typedef long long int ll;
typedef long double ld;
#define endl "\n"
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

ll const inf = 1e18;
ll const maxn = 1e6+5;
ll const mod = 1e9+7;

// code begins here

int main(){
    fast;
    
    string s, t;
    cin>>s>>t;
    
    ll n = t.length();
    
    if(s==t.substr(0,n-1)){
        cout<<"Yes"<<endl;
    } else {
        cout<<"No"<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 3616
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace lec09C
{
    class Program
    {
        static int size;
        public const int INF = 2000000009;

        static void Main(string[] args)
        {
            //setting part
            size = 0;
            int[] array = new int[2000000];
            bool flag = true;


            //main part
            while (flag)
            {
                string input = Console.ReadLine();
                string[] split = input.Split(' ');

                if (split[0] == "insert")
                {
                    MaxHeapInsert(array, int.Parse(split[1]));
                }
                if (split[0] == "extract")
                {
                    int k = HeapExtractMax(array);
                    Console.WriteLine("{0}", k);
                }
                if (split[0] == "end")
                {
                    flag = false;
                }
            }


            Console.ReadLine();
        }

        static void MaxHeapInsert(int [] arr, int key)
        {
            size++;
            arr[size-1] = -1 * INF;
            HeapIncreaseKey(arr, key);
        }

        static void HeapIncreaseKey( int [] arr , int key)
        {
            int i = size;
            if (key < arr[i-1])
            {
                Console.WriteLine("HeapIncreaseKey Error");
            }
            arr[i-1] = key;
            while (i > 1 && arr[(int)(i /2) -1] < arr[i -1])
            {
                int temp = arr[(int)(i / 2) - 1];
                arr[(int)(i / 2) - 1] = arr[i - 1];
                arr[i - 1] = temp;
                i = i/2;
            }
        }

       static int HeapExtractMax(int [] arr)
        {
            if (size < 1)
            {
                Console.WriteLine("HeapExtractMax Error");
            }
            int max = arr[0];
            arr[0] = arr[size - 1];
            size--;
            MaxHeapify(arr,1);
            return max;
        }

        static void BuildMaxHeap(int[] arr)
        {
            for (int i = size / 2; i > 0; i--)
            {
                MaxHeapify(arr, i);
            }
        }

        static void MaxHeapify(int[] arr, int i)
        {
            int l = i * 2;
            int r = i * 2 + 1;
            int largest;

            if (l <= size && arr[l - 1] > arr[i - 1])
            {
                largest = l;
            }
            else
            {
                largest = i;
            }
            if (r <= size && arr[r - 1] > arr[largest - 1])
            {
                largest = r;
            }

            if (largest != i)
            {
                int temp = arr[i - 1];
                arr[i - 1] = arr[largest - 1];
                arr[largest - 1] = temp;

                MaxHeapify(arr, largest);
            }
        }
    }
}


Measured memory_bytes: 22864
x1,y1,x2,y2=list(map(int,input().split()))

x3=x2-(y2-y1)
y3=y2+(x2-x1)
x4=x1-(y2-y1)
y4=y1+(x2-x1)

print(str(x3)+" "+str(y3)+" "+str(x4)+" "+str(y4))

Measured memory_bytes: 3060
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_variables)]

use proconio::{fastout, input};
use std::cmp::{max, min};
use std::fmt::{Display, Formatter};
use std::ops::{Add, Sub, Mul, Div};

const INF: i32 = 1001001001;
const LNF: i64 = 1001001001001001001;
const MOD: u32 = 1000000007;

#[fastout]
fn main() {
  input! {
    n: usize,
    m: usize,
  }
  let mc = ModCalc::new(500000);
  let all = (mc.facc[m] / mc.facc[m - n]).pow(2);
  let mut acc = ModInt(0);
  for i in 1..(n + 1) {
    let a = mc.facc[m] / mc.facc[m - i];
    let b = (mc.facc[m - i] / mc.facc[m - n]).pow(2);
    if i % 2 == 1 {
      acc = acc + mc.com(n, i) * a * b;
    } else {
      acc = acc - mc.com(n, i) * a * b;
    }
  }
  let ans = all - acc;
  println!("{}", ans);
}

trait Monoid {
  fn one() -> Self;
}

trait Powerable: Mul<Output = Self> + Monoid + Copy {
  fn pow(self, mut n: u64) -> Self {
    let mut r = Self::one();
    let mut x = self;
    while n > 0 { if n & 1 == 1 { r = r * x; } x = x * x; n >>= 1; }
    r
  }
}

#[derive(Clone, Copy)]
struct ModInt(u32);

impl Monoid for ModInt {
  fn one() -> Self { Self(1) }
}

impl Powerable for ModInt {}

impl Display for ModInt {
  fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
    write!(f, "{}", self.0)
  }
}

impl Add for ModInt {
  type Output = Self;
  fn add(self, rhs: Self) -> Self {
    let x = self.0 + rhs.0;
    Self(if x >= MOD { x - MOD } else { x })
  }
}

impl Sub for ModInt {
  type Output = Self;
  fn sub(self, rhs: Self) -> Self {
    let x = self.0 + MOD - rhs.0;
    Self(if x >= MOD { x - MOD } else { x })
  }
}

impl Mul for ModInt {
  type Output = Self;
  fn mul(self, rhs: Self) -> Self {
    let x = self.0 as u64 * rhs.0 as u64;
    Self(if x >= MOD as u64 { x % MOD as u64 } else { x } as u32)
  }
}

impl Div for ModInt {
  type Output = Self;
  fn div(self, rhs: Self) -> Self {
    self * rhs.inv()
  }
}

impl ModInt {
  fn new(x: u32) -> Self {
    Self(x % MOD)
  }
  fn inv(self) -> Self {
    self.pow((MOD - 2) as u64)
  }
}

struct ModCalc {
  facc: Vec<ModInt>,
  finv: Vec<ModInt>,
}

impl ModCalc {
  fn new(n: usize) -> Self {
    let mut facc = vec![ModInt(0); n + 1];
    let mut finv = vec![ModInt(0); n + 1];
    facc[0] = ModInt::one();
    for i in 0..n {
      facc[i + 1] = facc[i] * ModInt((i + 1) as u32);
    }
    finv[n] = ModInt::one() / facc[n];
    for i in (0..n).rev() {
      finv[i] = finv[i + 1] * ModInt((i + 1) as u32);
    }
    ModCalc { facc, finv }
  }
  fn com(&self, a: usize, b: usize) -> ModInt {
    if b > a {
      return ModInt(0);
    }
    self.facc[a] * self.finv[a - b] * self.finv[b]
  }
}

Measured memory_bytes: 6044
def main():
  if 'get_ipython' not in globals(): 
    #INPUT 
    k = int(input())
    s = input()

  else:
    #SAMPLE INPUT
    k = 7
    s = "nikoandsolstice"

  #SUBMITION CODES
  if len(s) <= k:
    print(s)
  else:
    print(s[:k]+"...")
    
main()

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

// typedef
using ll = long long;
using str = string;
using PL = pair<ll, ll>;
using P = pair<int, int>;
using VL = vector<ll>;
using vi = vector<int>;
using vs = vector<str>;
using vp = vector<P>;
using VPL = vector<PL>;
using VVL = vector<VL>;
using vvi = vector<vi>;

// const num
const ll INF = 1e18 + 18;
const ll MAX = 100005;
const ll MOD = 1000000007;
const long double PI = acosl(-1.0);

// Loop
#define REP(i, a, b) for (ll(i) = (a); (i) < (b); (i)++)
#define RREP(i, a, b) for (ll(i) = (a); (i) >= (b); (i)--)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, n, 0)

// YesNo
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define YES(n) cout << ((n) ? "YES" : "NO") << endl

// All
#define ALL(v) v.begin(), v.end()

int main(void)
{
    int a;
    cin >> a;
    cout << a * a * a + a * a + a << endl;
    return 0;
}

Measured memory_bytes: 3592
#ifdef _MSC_VER
#include "stdc++.h"
#endif
#ifdef __GNUC__
#include<bits/stdc++.h>
#endif
using namespace std;

using ll = long long;

//constant
const double EPS = 1e-10;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, s, e) for (ll i = s; i < e; i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(), (x).rend()

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;

// vector
//template<typename T> vector<vector<T>> vv(ll H, ll W, T v) { return vector<vector<T>> vec(H, vector<T>(W, v)); }

// view vector
template<typename T> void view(T e) { cout << e << endl; }
template<typename T> void view(const vector<T>& v) { for (const auto& e : v) { cout << e << " "; } cout << endl; }
template<typename T> void view(const vector<vector<T> >& vv) { for (const auto& v : vv) { view(v); } }

// DP
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; }




// ***************************************

int N, K, C;
vector<ll> calc(string S){
    int last = -1 - C;
    int cur = 0;
    vector<ll> ret(N + 1);
    REP(i, N){
        if(i - last > C && S[i] == 'o'){
            cur++;
            last = i;
        }
        ret[i + 1] = cur;
    }

    return ret;
}


int main(){

    string S, T;

    cin >> N >> K >> C >> S;
    T = S;
    reverse(ALL(T));

    const auto& left = calc(S);
    const auto& right = calc(T);

    bool flag = false;
    REP(i, N){
        if (left[i] + right[N - i - 1] < K && S[i] == 'o') {
            cout << i + 1 << endl;
            flag = true;
        }
    }
    if(!flag) cout << endl;

    return 0;
}


Measured memory_bytes: 5184
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#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'

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(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    string t;
    cin >> t;

    int n = t.size();

    rep(i, n){
        if(t[i] == '?'){
            t[i] = 'D';
        }
    }

    cout << t << endl;

    cout << flush;

    return 0;
}

Measured memory_bytes: 3748
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1<<30;
const ll LINF = 1LL<<60;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("input.in", "r")) {
        freopen("input.in", "r", stdin);
        freopen("output.out", "w", stdout);
    }

    string s;
    cin >> s;

    if (s == "ABC") cout << "ARC\n";
    else cout << "ABC";

    return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
  ll s,w;
  cin >> s >> w;
  if(s>w){
    cout << "safe" << endl;
  }
  else{
    cout << "unsafe" << endl;
  }
}


Measured memory_bytes: 3596
#include <cctype>
#include <cstdio>

using namespace std;

int k = 0;

char enc(char c) {
  return (c-'a'+k)%26+'a';
}

char dec(char c) {
  if (!islower(c))
    return c;
  return (c-'a'+26-k)%26+'a';
}

int main() {
  char s[128];
  while (fgets(s, 128, stdin)) {
    char *c = s;
state_delim:
    switch (*c) {
    case '.':
    case ' ':
      *c++;
      goto state_delim;
    case '\n':
      goto decode;
    default:
      goto state_start;
    }
state_start:
    if (islower(*c)) {
      k = (*c-'t'+26)%26;
      goto state_t;
    }
    goto state_delim;
state_t:
    *c++;
    if (islower(*c)) {
      if (*c == enc('h'))
        goto state_h;
      goto state_word;
    }
    goto state_delim;
state_h:
    *c++;
    if (islower(*c)) {
      if (*c == enc('e'))
        goto state_accept;
      if (*c == enc('i'))
        goto state_i;
      if (*c == enc('a'))
        goto state_a;
      goto state_word;
    }
    goto state_delim;
state_i:
    *c++;
    if (islower(*c)) {
      if (*c == enc('s'))
        goto state_accept;
      goto state_word;
    }
    goto state_delim;
state_a:
    *c++;
    if (islower(*c)) {
      if (*c == enc('t'))
        goto state_accept;
      goto state_word;
    }
    goto state_delim;
state_word:
    *c++;
    if (islower(*c))
      goto state_word;
    goto state_delim;
state_accept:
    *c++;
    if (!islower(*c))
      goto decode;
    goto state_word;
decode:
    c = s;
    while (*c)
      printf("%c", dec(*c++));
  }
}

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

int main()
{
	long long n; cin >> n;
	
	vector<long long> accum(n + 2, 0);
	accum[0] = 0;
	for (int i = 1; i <= n; i++) {
		long long tmp_a;
		cin >> tmp_a;
		accum[i] += tmp_a + accum[i - 1];

	}

	long long ans = 9223372036854775807LL;

	for (int i = 1; i < n; i++) {
		long long x = accum[i];
		long long y = accum[n] - accum[i];
		long long tmp = abs(x - y);
		ans = min(ans, tmp);
	}
		
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1792
#include <cstdio>

int main()
{
    int n;
    scanf("%d", &n);

    const int MOD = 1e9 + 7;
    long long answer = 1;

    for(int i = 1; i <= n; i++)
        answer = (answer*i)%MOD;

    printf("%lld\n", answer);

    return 0;
}


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

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

using ll = long long;
#define INF 1e9

int main(){ 
  int n;
  cin >> n;
  vector<int> p(n);
  REP(i, n){
    cin >> p[i];
  }
  int cnt = 0;
  FOR(i, 1, n-1){
    if(p[i] > min(p[i-1], p[i+1]) && p[i] < max(p[i-1], p[i+1])) cnt++;
  }
  cout << cnt << endl;
  return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <cctype>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
using namespace std;

int n,a[100100];

int getint()
{
    char ch;
    while (!isdigit(ch=getchar()));
    int x=ch-'0';
    for (; isdigit(ch=getchar()); x=x*10+ch-'0');
    return x;
}

int gcd(int x,int y)
{
    for (int t; t=x%y; x=y,y=t);
    return y;
}

int main()
{
    n=getint();
    repu(i,1,n)
        a[i]=getint();
    for (int i=1; 1; ++i)
    {
        int even=0,odd=0;
        repu(j,1,n)
            (a[j]&1?odd:even)++;
        if (even&1)
        {
            puts(i&1?"First":"Second");
            return 0;
        }
        if (odd>1)
        {
            puts(i&1?"Second":"First");
            return 0;
        }
        repu(j,1,n)
            if (a[j]&1)
            {
                if (a[j]==1)
                {
                    puts(i&1?"Second":"First");
                    return 0;
                }
                --a[j];
                break;
            }
        int d=a[1];
        repu(j,2,n)
            if ((d=gcd(d,a[j]))==1)
                break;
        if (d>1)
            repu(j,1,n)
                a[j]/=d;
    }
    return 0;
}

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

bool is_palindrome(string s){
  string t(s.rbegin(),s.rend());
  return s==t;
}
int main(){
  string s;
  cin>>s;
  int n=s.size();
  if(is_palindrome(s)&&is_palindrome(s.substr(0,(n-1)/2))&&is_palindrome(s.substr((n+1)/2))){
    cout<<"Yes";
  }
  else{
    cout<<"No";
  }
  return 0;
}

Measured memory_bytes: 256
from collections import deque
h,w = map(int, input().split())
l = [list(input()) for _ in range(h)]
ans = 0
def bfs(y,x,m):
  g = [[None if l[i][j] == '.' else -1 for j in range(w)] for i in range(h)]
  g[y][x] = 0
  q = deque()
  q.append((y,x))
  while q:
    i,j = q.popleft()
    for di,dj in ((0,1),(1,0),(-1,0),(0,-1)):
      ni = i+di; nj = j+dj
      if 0 <= ni < h and 0 <= nj < w and g[ni][nj] is None:
        g[ni][nj] = g[i][j] + 1
        q.append((ni,nj))
  return max(max(r) for r in g)

for i in range(h):
  for j in range(w):
    if l[i][j] == '.':
      d = bfs(i,j,l)
      if ans < d:
        ans = d
print(ans)

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

int main() {
  int N, L;
  cin >> N >> L;
  vector<string> vec(N);
  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  sort(vec.begin(),vec.end());
  
  string S ="";
  for (int i = 0; i < N; i++) {
    S += vec.at(i);
  }
  
  cout << S << endl;
}

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

int N;
vector<lint> a;

lint solve()
{
    lint sum = 0;
    lint ans = 0;
    for (int i = 0; i < N; i++)
    {
        sum += a[i];
        if (i%2 == 1)
        {
            if (sum <= 0)
            {
                ans += -sum + 1;
                sum = 1;
            }
        }
        else
        {
            if (sum >= 0)
            {
                ans += sum + 1;
                sum = -1;
            }
        }
    }
    return ans;
}
int main()
{
    cin >> N;
    a.resize(N);
    for (auto &v : a) cin >> v;
    lint res = solve();
    for (auto &v : a) v = -v;
    cout << min(res, solve()) << endl;
}

Measured memory_bytes: 1024
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    # 数値取得サンプル
    n = int(input())
    a_s = list(map(int, input().split()))

    # 和
    aaa = sum(a_s)

    ans = 0
    for cnt, a in enumerate(a_s):
        aaa -= a
        if aaa == 0:
            break

        ans += aaa * a
        ans = ans % (pow(10, 9) + 7)

    print(ans % (pow(10, 9) + 7))

    # テストクラス


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3
1 2 3"""
        output = """11"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4
141421356 17320508 22360679 244949"""
        output = """437235829"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_original(self):
        pass


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()


Measured memory_bytes: 96396
# include<bits/stdc++.h>
# define ll long long int
using namespace std;
int main(){
  
  char a[100],b[100];
  cin>>a>>b;
   ll count=0;
  for(int i=0;i<3;i++){
   
    if(a[i]==b[i])
      count++;
    
  }
  cout<<count;
  return 0;
  }

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

int main(){
  int s,w;cin>>s>>w;
  cout<<(s>w?"safe":"unsafe");
}


Measured memory_bytes: 3612
n, d = map(int, input().split())
ls_x = [[int(i) for i in input().split()] for i in range(n)]

cub_of_ds = 0
cnt = 0

for i in range(n):
    for j in range(n):
        for k in range(d):
            cub_of_ds += (ls_x[i][k] - ls_x[j][k])**2
        if (((cub_of_ds)**(1/2)).is_integer() == True) and (i > j):
            cnt += 1
        cub_of_ds = 0
        
print(cnt)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;

main(){
    string S;
    cin >> S;
    /*
    vector<int>cnt(S.size());
    rep(i,0,S.size()){
        if(S[i] == 'L')cnt[i-1]++;
        else cnt[i+1]++;
    }
    */
    vector<int> sum(S.size());
    //右向き
    int cnt = 0;
    rep(i,0,S.size()){
        if(S[i] == 'R'){
            cnt++;
        }else{
            sum[i-1] += (cnt+1) / 2;
            sum[i] += cnt / 2;
            cnt = 0;
        }
    }
    //左向き
    for(int i = S.size()-1; i >= 0;i--){
        if(S[i] == 'L'){
            cnt++;
        }else{
            sum[i+1] += (cnt+1) / 2;
            sum[i] += cnt / 2;
            cnt = 0;
        }
    }
    rep(i,0,S.size())cout << sum[i] << " ";
}

Measured memory_bytes: 1024
unittest
{
	assert( [ "4 2" ].parse.expand.solve == 3 );
	assert( [ "1 1" ].parse.expand.solve == 1 );
	assert( [ "15 11" ].parse.expand.solve == 5 );
}



import std.conv;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto ni = input.front.split.to!( long[] );
	
	return tuple( ni[ 0 ], ni[ 1 ] );
}

auto solve( long n, long i )
{
	return n + 1 - i;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s, t;
    int l, cnt=0;
    cin >> s >> t;
    l = s.size();
    for(int i=0; i<l; i++){
        if(s[i]>=65 && s[i]<=90){
            s[i] += 32;
            continue;
        }
        if(t[i]>=65 && t[i]<=90){
            t[i] += 32;
            continue;
        }
    }
    for(int i=0; i<l; i++){
        if(s[i] != t[i]) ++cnt;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 3912
#include <iostream>
#include <string>

using namespace std;

int main(){
	int r_num = 0, ans = 0;
	string s;
	int n;
	cin >> n;
	cin >> s;
	int size = s.size();
	for (int i = 0; i < size; i++)
		if (s[i] == 'R') r_num += 1;
	for (int i = 0; i < r_num; i++)
		if (s[i] == 'W') ans += 1;
	cout << ans << '\n';
}


Measured memory_bytes: 3704
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <map>
#include <set>

#define INF 1000000007 //1000000000000000003
#define MOD 1000000007
#define MAX 2000005

#define ll long long

//printf("%.10f", );
//cout << fixed << setprecision(10) << heikin << endl;
//vector<vector<int>> data(3, vector<int>(4, -1));
//left + 1 < top

using namespace std;
using P = pair<int, int>;
using Pc = pair<double, int>;
using T = tuple<int, int, int>;
using edge = struct { int to; long long dist; };
const double PI = 3.1415;
long long fact[MAX], inv[MAX];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };

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

vector<vector<int>> bingo(3, vector<int>(3));
vector<vector<int>> tree(100005);
int color[100005];
map<P, int>colorMap;
int m = 0;

struct BridgeInfo {
	int town1;
	int town2;
	int year;
	BridgeInfo(int t1, int t2, int y) {
		town1 = t1;
		town2 = t2;
		year = y;
	}
};

struct People {
	int index;
	int town;
	int year;
	People(int i, int t, int y) {
		index = i;
		town = t;
		year = y;
	}
};

bool compare_by_second(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

struct UnionFind {
	vector<int>uf;

	UnionFind(int size) :uf(size, -1) {};

	int root(int target) {
		if (uf[target] < 0)return target;
		else return uf[target] = root(uf[target]);
	}

	void merge(int a, int b) {
		a = root(a);
		b = root(b);
		if (a == b)return;
		if (uf[b] < uf[a])swap(a, b);
		uf[a] += uf[b];
		uf[b] = a;
	}
};

ll CalcPow(ll num, ll power) {
	if (power == 0)return 1;
	if (power % 2 == 0) {
		ll half = CalcPow(num, power / 2);
		return (half * half) % MOD;
	}
	else return (num * CalcPow(num, power - 1)) % MOD;
}

ll combination(ll all, ll select) {
	if (all < select) return 0;
	if (all < 0 || select < 0) return 0;
	return fact[all] * (inv[select] * inv[all - select] % MOD) % MOD;
}

void initCombination(int max) {
	fact[0] = fact[1] = 1;
	for (int i = 2; i <= max; ++i) {
		fact[i] = fact[i - 1] * i % MOD;
	}

	inv[max] = CalcPow(fact[max], MOD - 2);
	for (int i = max - 1; 0 <= i; --i) {
		inv[i] = (inv[i + 1] * (i + 1)) % MOD;
	}
}

ll getGcd(ll a, ll b) {
	if (a < b) {
		ll temp = b;
		b = a;
		a = temp;
	}

	ll r;
	while ((r = a % b) != 0) {
		a = b;
		b = r;
	}
	return b;
}

int main() {
	int N, K; cin >> N>> K;
	map<int, int>sweet;
	for (int i = 0; i < K;++i) {
		int d; cin >> d;
		for (int j = 0; j < d;++j) {
			int a; cin >> a;
			sweet[a] = 1;
		}
	}
	int ans = N - sweet.size();
	cout << ans << endl;
}



Measured memory_bytes: 5396
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner scn = new Scanner(System.in);
    	int m = scn.nextInt();
    	int n = scn.nextInt();
      int sum = 0;
      if(n>0){
        sum += n*(n-1)/2;
      }
      if(m>0){
        sum += m*(m-1)/2;
      }
      System.out.println(sum);
	}
}


Measured memory_bytes: 22228
#include<bits/stdc++.h>
#define M 1000000007
#define pi ld(acos(-1.0))
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,n) for(int i=1;i<(int)(n);i++)
#define repp(i,a,b)  for(ll i=a;i<=(ll)(b);i++)
#define Repp(i,a,b)  for(int i=a;i>=(int)(b);i--)
#define cs ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define ii pair<int,int>
#define bye(x) {cout<<x;return 0;}
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    cs
    int n;cin>>n;
    vector<ld> v(n);
    for(auto &i:v) cin>>i;
    vector<vector<ld>> dp(n+1,vector<ld>(n+1));
    dp[0][0]=1;
    repp(i,1,n) {
        repp(j,0,i) {
            dp[i][j]+=dp[i-1][j]*(1-v[i-1]);
            if(j) dp[i][j]+=dp[i-1][j-1]*v[i-1];
        }
    }
    ld ans=0;
    repp(i,n/2+1,n) ans+=dp[n][i];
    cout<<fixed<<setprecision(12)<<ans;
}

Measured memory_bytes: 141056
S=str(input())
N=len(S)
M=int((N-1)/2)
sum=0
for i in range(N):
    if S[i]==S[-1-i]:
        sum += 1
for i in range(M):
    if S[i]==S[M-i-1]:
        sum += 1
for i in range(M+1,N):
    if S[i]==S[M-i]:
        sum += 1
if sum==2*N-1:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
 
int main() {
	int a, b, c, d, e, f;
	std::cin >> a >> b >> c >> d >> e >> f;
	a *= 100;
	b *= 100;
 
	std::vector<int> water, suger;
	for (int i = 0; a * i <= f; ++i)
		for (int j = 0; a * i + b * j <= f; ++j)
			water.push_back(a * i + b * j);
 
	for (int i = 0; c * i <= f; ++i)
		for (int j = 0; c * i + d * j <= f; ++j)
			suger.push_back(c * i + d * j);
 
	int ansTotal = 0, ansSuger = 0;
	double maxDens = -1.0;
	for (auto&& w : water) {
		for (auto&& s : suger) {
			if (w + s <= f && s <= w / 100 * e) {
				const double dens = 1.0 * s / (w + s);
				if (dens > maxDens) {
					maxDens = dens;
					ansTotal = w + s;
					ansSuger = s;
				}
			}
		}
	}
 
	std::cout << ansTotal << " " << ansSuger << std::endl;
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> data(N);
  for(int i = 0; i < N; i++){
    cin >> data[i];
  }
  int64_t count_odd, count_even;
  count_odd = 0;
  count_even = 0;
  int64_t sum_odd = 0;
  int64_t sum_even = 0;
  for(int i = 0; i < N; i++){
    sum_even += data[i];
    if(i%2 == 0){
      if(sum_even >= 0){
        count_even += (sum_even + 1);
        sum_even = -1;
      }
    }
    else{
      if(sum_even <= 0){
        count_even -= (sum_even - 1);
        sum_even = 1;
      }
    }
  }
  for(int i = 0; i < N; i++){
    sum_odd += data[i];
    if(i%2 == 0){
      if(sum_odd <= 0){
        count_odd -= (sum_odd - 1);
        sum_odd = 1;
      }
    }
    else{
      if(sum_odd >= 0){
        count_odd += (sum_odd + 1);
        sum_odd = -1;
      }
    }
  }
  cout << min(count_even, count_odd)  << endl;
}




Measured memory_bytes: 640
#include<cstdio>
#include<algorithm>
using namespace std;
static const int MAX_M = 10000;
static const int MAX_N = 500;

int M, N;
int P[MAX_M + 1];
int C[MAX_N + 1], E[MAX_N + 1];
int memo[MAX_N + 1][MAX_M + 1];

int main(){
	scanf("%d %d", &M, &N);
	for(int i = 1; i < M + 1; i++) scanf("%d", &P[i]);
	for(int i = 1; i < N + 1; i++) scanf("%d %d", &C[i], &E[i]);

	fill(memo[0], memo[N + 1], 1 << 30);
	sort(P, P + M + 1);
	reverse(P + 1, P + M + 1);
	for(int i = 1; i < M + 1; i++) P[i] += P[i - 1];

	for(int i = 0; i < N + 1; i++){
		for(int j = 0; j < M + 1; j++){
			if(j == 0) memo[i][j] = 0;
			else if(i == 0) continue;
			else if(j < C[i]) memo[i][j] = min(memo[i - 1][j], E[i]);
			else memo[i][j] = min(memo[i - 1][j], memo[i - 1][j - C[i]] + E[i]);
		}
	}
	int res = 0;
	for(int i = 0; i < M + 1; i++){
		if(memo[N][i] == 1 << 30) break;
		res = max(res, P[i] - memo[N][i]);
	}
	printf("%d\n", res);
	return 0;
}



Measured memory_bytes: 22416
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int[] h = new int[n];
    int[] DP = new int[n];
    Arrays.fill(DP,Integer.MAX_VALUE);

    for(int i=0; i<n; i++){
      h[i] = sc.nextInt();
    }

    DP[0] = 0;
    DP[1] = Math.abs(h[1] -h[0]);

    for(int i=2; i<n; i++){
      for(int j=1; j<=k;j++){
        DP[i] = Math.min(DP[i],DP[i-j]+Math.abs(h[i]-h[i-j]));
        if(i-j==0){break;}
      }

    }

    System.out.println(DP[n-1]);

  }
}

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

int main(void){
    
    string N;
    
    while(true){
        cin >> N;
        if(N[0] == '0') break;
        
        int ans = 0;
        for(int i = 0; i < N.size(); i++){
            ans += N[i] - '0';
        }
        cout << ans << endl;
    }
    
}



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

int main() {

    string s;

    cin >> s;

    map<char,int> m;

    for(auto i : s){
        m[i]++;
    }

    if(m['a'] == m['b'] && m['b'] == m['c'] && m['a'] == 1){
        cout << "Yes" << endl;
        return 0;
    }

    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
n = int(input())
li = []
for i in range(n):
  a = list(map(int, input().split()))
  li.append(a)
dp = []
for i in range(n):
  dp.append([0 for j in range(3)])
dp[0][0] = li[0][0]
dp[0][1] = li[0][1]
dp[0][2] = li[0][2]
for i in range(1, n):
  dp[i][0] = li[i][0] + max(dp[i-1][1], dp[i-1][2])
  dp[i][1] = li[i][1] + max(dp[i-1][0], dp[i-1][2])
  dp[i][2] = li[i][2] + max(dp[i-1][0], dp[i-1][1])
print(max(dp[n-1][0], dp[n-1][1], dp[n-1][2]))

Measured memory_bytes: 47408
// https://atcoder.jp/contests/dp/tasks/dp_a

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)

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

    dp[0] = 0;
    dp[1] = abs(h[0]-h[1]);
    for(int i=2;i<N;i++){
        dp[i] = min(dp[i-1] + abs(h[i]-h[i-1]), dp[i-2] + abs(h[i]-h[i-2]));
    }
    cout << dp[N-1] << endl;
}

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

int main() {
  int n;
  ll ans=0;
  cin >> n;
  rep(i,n+1){
    if(!(i%3==0||i%5==0)){
      ans+=i;
    }
  }
  cout <<ans<<endl;
}


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

int main()
{
  int n;
  string s;
  cin >> n >> s;
  if(n >= 3200){
    cout << s << endl;
  }
  else {
    cout << "red" << endl;
  }
  return 0;
}

Measured memory_bytes: 3628
import java.util.*;
public class Main {
	public static void main(String[] args)  {
		Scanner scan = new Scanner(System.in);
		int n = Integer.parseInt(scan.next());
		int m = Integer.parseInt(scan.next());
		int[] h = new int[n];
		for (int i = 0;i < n; ++i){
			h[i] = Integer.parseInt(scan.next());
		}
		boolean[] good = new boolean[n];
		Arrays.fill(good, true);

		int a,b;
		for (int i = 0;i < m; ++i){
			a = Integer.parseInt(scan.next());
			b = Integer.parseInt(scan.next());
			if (h[a-1] > h[b-1]){
				good[b-1] = false;
			}else if(h[a-1] < h[b-1]) {
				good[a-1] = false;
			}else if (h[a-1] == h[b-1]){
				good[b-1] = false;
				good[a-1] = false;
			}
		}

		int ans = 0;
		for (boolean i:good){
			if (i)++ans;
		}
		System.out.print(ans);
	}
}

//end

Measured memory_bytes: 59408
#include <bits/stdc++.h>
#define rep(i, s, n) for (int i = s; i < (n); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
ll mod = 1000000007;
//---------------------------------------------------------------------------------------------------
ll f[101010], rf[101010];
ll inv(ll x)
{
    ll res = 1;
    ll k = mod - 2;
    ll y = x;
    while (k)
    {
        if (k & 1)
            res = (res * y) % mod;
        y = (y * y) % mod;
        k /= 2;
    }
    return res;
}
void init()
{
    f[0] = 1;
    rep(i, 1, 101010) f[i] = (f[i - 1] * i) % mod;
    rep(i, 0, 101010) rf[i] = inv(f[i]);
}
//---------------------------------------------------------------------------------------------------
ll C(int n, int k)
{
    ll a = f[n];      // = n!
    ll b = rf[n - k]; // = (n-k)!
    ll c = rf[k];     // = k!

    ll bc = (b * c) % mod;

    return (a * bc) % mod;
}

ll P(int n, int k)
{
    if (n < k)
    {
        return 0;
    }
    ll a = f[n];
    ll b = rf[n - k];
    return (a * b) % mod;
}
bool fl[100010];
vector<int> v[100010];
ll ans = 1;
int n, k;
void dfs(int node, int level)
{
    fl[node] = true;
    if (level == 0)
    {
        ans *= P(k, v[node].size() + 1);
        ans %= mod;
    }
    else
    {
        ans *= P(k - 2, v[node].size() - 1);
        ans %= mod;
    }
    for (auto i : v[node])
    {
        if (fl[i])
            continue;
        dfs(i, level + 1);
    }
    return;
}
int main()
{
    init();
    cin >> n >> k;
    ans = 1;
    REP(i, n - 1)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1, 0);
    cout << ans % mod << endl;
}


Measured memory_bytes: 9728