akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

void solve(){
    ll n;
    cin >> n;
    Vi p(n-1);
    Vi x(n);
    rp(i,n-1) cin >> p[i];
    rp(i,n) cin >> x[i];
    bool ok=true;
    vector<vector<PLL>> mat(n);
    for(ll i=n-1; i>=0; i--){
        vector<ll> dp(5003,0);
        dp[0]=1;
        ll sum=0;
        for(PLL pl:mat[i]){
            //princ(pl.first);
            //print(pl.second);
            sum += pl.first+pl.second;
            for(ll j=5000; j>=0; j--){
                if(dp[j]==0) continue;
                dp[j]=0;
                if(j+pl.first<=5000) dp[j+pl.first]=1;
                if(j+pl.second<=5000) dp[j+pl.second]=1;
            }
        }
        ll pos=x[i];
        bool found=false;
        while(pos>=0){
            if(dp[pos]==1){
                if(i>0) {
                    if(pos>sum-pos||x[i]<sum-pos) mat[p[i-1]-1].pb(mp(x[i],sum-pos));
                    else mat[p[i-1]-1].pb(mp(x[i],pos));
                }
                found=true;
                break;
            }
            pos--;
        }
        if(!found) {
            ok=false;
            break;
        }
        //print(i);
    }
    if(ok) print("POSSIBLE");
    else print("IMPOSSIBLE");
    return;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    solve();
    return 0;
}

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

using namespace std;

int main(void)
{
	string ss; cin>>ss; int len = ss.size();
	int s[len]; for(int i = 0; i < len; i++) s[i] = (int)ss[i];
	if(s[0] == s[1]){
		cout<<"1 2"<<endl;
		return 0;
	}
	for(int i = 0; i < len-2; i++){
		if(s[i] == s[i+1]){
			cout<<i+1<<" "<<i+2<<endl;
			return 0;
		}
		else if(s[i] == s[i+2]){
			cout<<i+1<<" "<<i+3<<endl;
			return 0;
		}
		else if(s[i+1] == s[i+2]){
			cout<<i+2<<" "<<i+3<<endl;
			return 0;
		}
	}
	
	cout<<"-1 -1"<<endl;
	
	return 0;
}



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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

const int INF = 1001001001;

int main() {
    int N, X, Y;
    cin >> N >> X >> Y;
    X--, Y--;
    vector<int> ans(N);

    // BFS
    rep(sv, N) {
        vector<int> dist(N, INF);
        queue<int> q;
        auto push = [&](int v, int d) {
            if (dist[v] != INF) return;
            dist[v] = d;
            q.push(v);
        };

        push(sv, 0);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            int d = dist[v];
            if (v - 1 >= 0) push(v - 1, d + 1);
            if (v + 1 < N) push(v + 1, d + 1);
            if (v == X) push(Y, d + 1);
            if (v == Y) push(X, d + 1);
        }

        rep(i, N) ans[dist[i]]++;
    }

    rep(i, N) ans[i] /= 2;
    for (int i = 1; i < N; i++) {
        cout << ans[i] << endl;
    }
}


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

using namespace std;

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

	vector<int> ruisekiW(n+1,0);
	vector<int> ruisekiE(n+1,0);

	for(int i=1;i<=n;i++){
		ruisekiW.at(i)=ruisekiW.at(i-1);
		ruisekiE.at(i)=ruisekiE.at(i-1);

		if(s.at(i-1)=='W') ruisekiW.at(i)++;
		else ruisekiE.at(i)++;
	}

	int ans=4*pow(10,5);

	for(int i=0;i<n;i++){
		int hoge=ruisekiW.at(i) + ruisekiE.at(n)-ruisekiE.at(i+1);
		ans=min(ans,hoge);
	}

	cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 3076
#include <iostream>
#include <cstdio>
using namespace std;
 
int main() {
	int a,b,d,r;
	double f;
	cin >> a >> b;
	d = a/b;
	r = a%b;
	f = double(a)/double(b);
	printf("%d %d %lf\n",d,r,f);
	return 0;
}

Measured memory_bytes: 3216
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
using pii = pair<int, int>;
const int MOD = 1e9 + 7;
const int INF = 1 << 29;
const int N = 1e5 + 10;
 
struct IOsetup{
  IOsetup(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); 
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
  }
}IO;
vector<int> primes;
bool isprime[N];

void init_primes(){
  fill (isprime + 2, isprime + N, true);
  for (int i = 2; i < N; i++){
    if (isprime[i]){
      primes.push_back(i);
      for (int j = 2; i * j < N; j++){
        isprime[i * j] = false;
      }
    }
  }
}

int32_t main(){
  init_primes();
  int n;
  cin >> n;
  auto it = *lower_bound(primes.begin(), primes.end(), n);
  cout << it << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a[100005],b[100005],c[100005];
  int n;
  cin>>n;
  for(int i=0; i<n; i++){
    cin>>a[i]>>b[i]>>c[i];
  }
  for(int i=1; i<n; i++){
    a[i]+=max(b[i-1],c[i-1]);
    b[i]+=max(a[i-1],c[i-1]);
    c[i]+=max(a[i-1],b[i-1]);
  }
  
  cout<<max(a[n-1],max(b[n-1],c[n-1]))<<'\n';
  return 0;
}


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

int main(){
  int n;cin >> n;
  vector<int> a(n);
  int cnt4=0,cnt2=0,cnt_else=0;
  for(int i=0;i<n;i++){
    cin >> a[i];
    if(a[i]%4==0){
      cnt4++;
    }else if(a[i]%2==0){
      cnt2++;
    }else{
      cnt_else++;
    }
  }
  if(cnt4>=(cnt_else-1)+cnt2%2){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define int long long
const ll INF = 1e15;

const int N = 150 * 1000 + 1000;
vector<int> adj[N];
double dp[N], up[N];
int kid[N];

void sfd(int p, int par = 0){
	if(p != 0){
		if(par == 0 && kid[par] != 1)
			up[p] = (dp[par] * kid[par] - dp[p] - 1) / (kid[par] - 1) + 1;
		else if(par == 0 && kid[par] == 1)
			up[p] = 1;
		else if(par != 0)
			up[p] = (dp[par] * kid[par] - dp[p] + up[par] - 1) / kid[par] + 1;
	}
	for(auto q : adj[p])
		if(q != par)
			sfd(q, p);
}

void dfs(int p, int par = 0){
	kid[p] = adj[p].size();
	if(p != 0)
		kid[p]--;

	for(auto q : adj[p])
		if(q != par){
			dfs(q, p);
			dp[p] += (dp[q] + 1) / kid[p];
		}
}

int32_t main(){
	ios::sync_with_stdio(false);cin.tie(0);
	
	int n;
	cin >> n;
	for(int i = 0; i < n - 1; i++){
		int u, v;
		cin >> u >> v;
		u--;v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	dfs(0);
	sfd(0);

	cout << fixed << setprecision(10);
	cout << dp[0] << '\n';
	for(int i = 1; i < n; i++){
		double ans = dp[i] * kid[i];
		ans += up[i];
		ans /= (kid[i] + 1);
		cout << ans << '\n';
	}
    return 0;
}

// Tu te faufiles
// entre mes lignes
// Tu te faufiles
// entre mes lignes
// Charlotte Cardin - Faufile

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

///Author:Refat(BSMRSTU)///

#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define pb push_back
#define vi vector<int>
#define pii pair<int,int>
#define pil pair<int,ll>
const int N = 1e5 + 5;
const int M = 1e9 + 7;
double pi=2*acos(0.0);
int Set(int N,int pos) {
    return N=N | (1<<pos);
}
int reset(int N,int pos) {
    return N= N & ~(1<<pos);
}
bool check(int N,int pos) {
    return (bool)(N & (1<<pos));
}
int ar[100];
int main() {
    /// freopen("input.txt","r",stdin);
    /// freopen("output.txt","w",stdout);
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&ar[i]);
    }
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            ans+=(ar[i]*ar[j]);
        }
    }
    printf("%d\n",ans);
    return 0;
}



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

int a[100];

int main(){
	int n,m,i,j,k,br=0,x;
	cin >> n >> m;
	for(i=0;i<n;i++){
		cin >> k;
		for(j=0;j<k;j++){
			cin >> x;
			a[x]++;
		}
	}
	for(i=1;i<=m;i++)
		if(a[i]==n)
			br++;
	cout << br;
}


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

long long max(long long a, long long b){return (a>b)?a:b;}

long long knapsack(long long w, long long wt[], long long val[], long long n)
{
    long long i,j;
    long long k[n+1][w+1];

    //build table k[][]
    for(i = 0; i <= n; i++)
    {
        for(j = 0; j <= w; j++)
        {
            if(i == 0 || j == 0) k[i][j] = 0;
            else if (wt[i - 1] <= j)
                k[i][j] = max(val[i-1] + k[i-1][j-wt[i-1]],k[i-1][j]);
            else
                k[i][j] = k[i-1][j];
        }
    }
    //cout<<"k["<<n<<"]["<<w<<"] = "<<k[n][w]<<"\n";

    return k[n][w];

}

int main()
{
    long long n,w;

    cin>>n>>w;
    long long wt[n+1];
    long long val[n+1];
    for(long long i = 0; i < n; i++)
    {
        cin>>wt[i]>>val[i];
    }
    cout<<knapsack(w,wt,val,n)<<"\n";

    return 0;
}
/*
6 15
6 5
5 6
6 4
6 6
3 5
7 2


3 8
3 30
4 50
5 60
*/


Measured memory_bytes: 79104
#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>;
const int MAX = 1000;
const int INF = 1e9;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
#define PI 3.14159265358979323846264338327950L

int main() {
	int N; cin >> N;
	vector<unsigned long long> v;
	vector<unsigned long long> w;
	rep(i,N) {
		int temp;
		cin >> temp;
		v.push_back(temp);
		if (i==0) w.push_back(temp);
		else w.push_back(temp+w[i-1]);
	}
	unsigned long long ans = 0;
	unsigned long long max = 1e9 + 7;
	for (int ii = 0; ii < N; ii++) {
		unsigned long long temp = w[N-1]-w[ii];
		unsigned long long temp2;
		temp2 = (ans % max) + (v[ii] % max) * (temp % max);
		ans = temp2 % max;
	}
	cout << ans << endl;
}

Measured memory_bytes: 6640
package main

import (
	"bufio"
	"fmt"
	basicIO "io"
	"os"
	"strconv"
)

func main() {
	protagonist(os.Stdin, os.Stdout)
}

func protagonist(r basicIO.Reader, w basicIO.Writer) {
	io := NewIO(r, w)
	A, _ := io.nextInt()
	B, _ := io.nextInt()
	T, _ := io.nextInt()

	io.PutInt((T / A) * B)
}

type IO struct {
	Scanner *bufio.Scanner
	Writer  basicIO.Writer
}

func NewIO(r basicIO.Reader, w basicIO.Writer) *IO {
	s := bufio.NewScanner(r)
	s.Split(bufio.ScanWords)
	return &IO{
		Scanner: s,
		Writer:  w,
	}
}

func (io *IO) nextString() string {
	io.Scanner.Scan()
	return io.Scanner.Text()
}

func (io *IO) nextInt() (int, error) {
	io.Scanner.Scan()
	i, err := strconv.Atoi(io.Scanner.Text())
	return i, err
}

func (io *IO) PutInt(v int) {
	fmt.Fprintf(io.Writer, "%d\n", v)
}

func (io *IO) PutString(s string) {
	fmt.Fprintf(io.Writer, "%s\n", s)
}


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

int main(){
int a,b,c;cin>>a>>b>>c;
int d=a+b+c;
if(d==2*max(a,max(b,c)))cout<<"Yes";
else cout<<"No";

}

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

const int W = 8;

char t[W + 2][W + 2];

void dfs(int x, int y){
  if(x < 0 || W <= x || y < 0 || W <= y) return;
  if(t[y][x] == '0') return;
  t[y][x] = '0';

  for(int i = -3; i <= 3; i++){
    dfs(x, y + i);
    dfs(x + i, y);
  }
}

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

  for(int DATA = 1; DATA <= T; DATA++){
    cout << "Data " << DATA << ":" << endl;
    for(int i = 0; i < W; i++){
      cin >> t[i];
    }

    int sx, sy;
    cin >> sx >> sy;
    dfs(sx - 1, sy - 1);

    for(int i = 0; i < W; i++){
      cout << t[i] << endl;
    }
  }
}

Measured memory_bytes: 1168
#include<bits/stdc++.h>
using namespace std;
int main()
{
   long long int n,a[100000],f=0,even=0;
   cin>>n;
   for(int i=0;i<n;i++)
   {
       cin>>a[i];
   }
   for(int j=0;j<n;j++)
   {
       if(a[j]%2==0)
       {
           even+=1;
           if(a[j]%3==0 |a[j]%5==0)
           {
               f++;
           }
          
       }
   }
      if(f==even)
       {
           cout<<"APPROVED"<<endl;
       }
       else
       {
           cout<<"DENIED"<<endl;
       }
    
}

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

int main() {
  int n,ans=10000;
  cin >> n;
  rep(i,n){
    int a,count=0;
    cin >> a;
    while(a%2==0){
        count++;
        a/=2;
    }
    ans = min({ans,count});
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,x,n) for(int i=(x);i<(n);i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define ub upper_bound
#define lb lower_bound
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;

signed main(){
  vector<int> v(101);
  int n;
  while(cin>>n)v[n]++;
  auto p= *max_element(v.begin(),v.end());
  rep(i,101)if(v[i]==p)cout<<i<<endl;
  return 0;
}

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

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

      long long q,n,k,i,count=0,j=0,l,r,ans=0,p,m,x;
      cin>>n;
      if(n==1)
      {
          cout<<1; return 0;
      }
      count=1;
      while(n>0)
      {
          ans+=count;
          n=n/2;
          count=count*2;
      }
      cout<<ans;
      
    
	return 0;
}

Measured memory_bytes: 256
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<usize>();
    let mut a = read::<String>()
        .chars()
        .map(|x| x.to_digit(10).unwrap() as i32)
        .collect::<Vec<_>>();

    let mut a = (1..n).map(|x| (a[x] - a[x - 1]).abs()).collect::<Vec<_>>();
    let n = a.len();

    let one_found = a.iter().filter(|&&x| x == 1).count() > 0;
    if one_found {
        a = a.iter().map(|&x| x % 2).collect::<Vec<_>>();
    } else {
        a = a.iter().map(|&x| x / 2).collect::<Vec<_>>();
    }

    let mut mul2 = vec![0i64; n + 1];
    for i in 0..n + 1 {
        let mut j = i;
        while j & 1 == 0 && j > 0 {
            mul2[i] += 1;
            j >>= 1;
        }
    }
    let mut accum_mul2 = vec![0; n + 1];
    for i in 1..n + 1 {
        accum_mul2[i] = mul2[i] + accum_mul2[i - 1];
    }

    let mut ans = 0;
    for i in 0..n {
        if a[i] == 0 {
            continue;
        }
        if accum_mul2[n - 1] - accum_mul2[i] - accum_mul2[n - 1 - i] == 0 {
            ans ^= 1;
        }
    }
    if !one_found {
        ans *= 2;
    }
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 28916
#include<iostream>
#include <algorithm>

using namespace std;

int main(){
  int N;cin>>N;
  int K;cin>>K;
  int H[N];
  for (int i = 0; i < N; i++)cin >>H[i];
  sort(H, H+N, greater<>());
  if(K<=N){
  for(int k=0;k<K;k++)H[k]=0;
  long sum=0;
  for(int n=K;n<N;n++)sum+=H[n];
  cout<<sum<<"\n";
  }
  else{
    cout<<0<<"\n";
  }
}

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

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  vector<int> b(n);
  for(int i=0; i<n; i++) {
    cin >> a.at(i) >> b.at(i);
  }
  vector<int> c(m);
  vector<int> d(m);
  for(int i=0; i<m; i++) {
    cin >> c.at(i) >> d.at(i);
  }
  for(int i=0; i<n; i++) {
    int mindis = 1000000000;
    int ans = 0;
    for(int j=0; j<m; j++) {
      int x = c.at(j) - a.at(i);
      if(x<0) x = -x;
      int y = d.at(j) - b.at(i);
      if(y<0) y = -y;
      int dis = x + y;
      if(dis < mindis) {
        mindis = dis;
        ans = j+1;
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 256
#include <cmath>
#include <vector>
#include <iomanip>
#include <iostream>
using namespace std;
int n; double px[209], py[209], pz[209], vx[209], vy[209], vz[209], r[209], vr[209], t[209][209], ret[209];
int main() {
	while (cin >> n, n) {
		for (int i = 0; i < n; i++) cin >> px[i] >> py[i] >> pz[i] >> vx[i] >> vy[i] >> vz[i] >> r[i] >> vr[i];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				// ((px[i] + t * vx[i]) - (px[j] + t * vx[j])) ^ 2 + ... == ((r[i] - t * vr[i]) + (r[j] - t * vr[j])) ^ 2
				t[i][j] = 1.0e+9;
				double cx1 = vx[i] - vx[j], cx0 = px[i] - px[j];
				double cy1 = vy[i] - vy[j], cy0 = py[i] - py[j];
				double cz1 = vz[i] - vz[j], cz0 = pz[i] - pz[j];
				double cr1 = vr[i] + vr[j], cr0 = -(r[i] + r[j]);
				double dx2 = cx1 * cx1 + cy1 * cy1 + cz1 * cz1 - cr1 * cr1;
				double dx1 = 2 * (cx1 * cx0 + cy1 * cy0 + cz1 * cz0 - cr1 * cr0);
				double dx0 = cx0 * cx0 + cy0 * cy0 + cz0 * cz0 - cr0 * cr0;
				double D = dx1 * dx1 - 4 * dx2 * dx0;
				if (i == j || D < 0.0) continue;
				double alpha = (-dx1 - sqrt(D)) / (2 * dx2);
				if (alpha > 0.0) t[i][j] = alpha;
			}
		}
		for (int i = 0; i < n; i++) ret[i] = r[i] / vr[i];
		while(true) {
			int mi = -1, mj = -1;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (t[i][j] < ret[i] && t[i][j] < ret[j]) {
						if (mi == -1 || t[mi][mj] > t[i][j]) mi = i, mj = j;
					}
				}
			}
			if (mi == -1) break;
			ret[mi] = t[mi][mj];
			ret[mj] = t[mi][mj];
		}
		for (int i = 0; i < n; i++) cout << fixed << setprecision(15) << ret[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 3520
#include "bits/stdc++.h"
#include <set>

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define int long long
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
#define mod 1000000007
#define INF 10e10
template <typename T>

void print(T x)
{
	std::cout << x << " ";
}

template <typename T>

void println(T x)
{
	std::cout << x << "\n";
}


signed main(void) {
	string s;
	cin >> s;
	int n = s.size();
	vector<int>a(n, 0);
	vector<int>ret(n, 0);
	int countr = 0;
	int countl = 0;
	rep(i, n) {
		if (s[i] == 'R') {
			countr++;
			a[i] = countr;
		}
		else countr = 0;
	}
	rrep(i, n) {
		if (s[i] == 'L') {
			countl++;
			a[i] = countl;
		}
		else countl = 0;
	}
	rep(i, n-1) {
		if (s[i] == 'R'&&s[i + 1] == 'L') {
			ret[i] += (a[i] + 1) / 2;
			ret[i+1] += a[i]/ 2;
			ret[i+1] += (a[i+1] + 1) / 2;
			ret[i] += a[i+1] / 2;
		}
	}
	for (auto b : ret) {
		print(b);
	}
}

Measured memory_bytes: 5108
graphs = []
loop do
  n = gets.chomp.to_i
  break if n == 0

  graph = []
  total = Array.new(n+1, 0)
  n.times do
    line = gets.chomp.split(' ').map(&:to_i)
    line_sum = 0
    line.each do |cell|
      line_sum += cell
    end
    line << line_sum
    graph << line

    total = total.zip(line).map{|x, y| x + y}
  end

  graph << total
  graphs << graph
end

graphs.each do |graph|
  graph.each do |line|
    puts line.map{|cell|"%5d" % cell}.join
  end
end

Measured memory_bytes: 6116
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll gcd(ll x,ll y){
    if(x>y)swap(x,y);
    if(y%x==0)return x;
    return gcd(x,y%x);
};

vector<ll> factor(ll x){
    vector<ll> prime;
    for (ll i = 2; i<=sqrt(x); i++) {
        if(x%i==0){
            while(x%i==0)x/=i;
            prime.push_back(i);
        }
        if(x==1)break;
    }
    if(x!=1)prime.push_back(x);
    prime.insert(prime.begin(),1);
    return prime;
}

int main(){
    ll a,b;
    cin >> a >> b;
    ll g=gcd(a,b);
    vector<ll> prime=factor(g);
    cout << prime.size() << endl;
}

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

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

  int count = 0;

  regex re("ABC");
  sregex_iterator ite(S.begin(), S.end(), re);
  sregex_iterator end;

  smatch match;

  for (; ite != end; ++ite) {
    count++;
  }

  cout << count << endl;
}

Measured memory_bytes: 256
s = input()
a = int(s[0])
b = int(s[1])
c = int(s[2])
d = int(s[3])
if a+b+c+d == 7:
    print(s[0]+"+"+s[1]+"+"+s[2]+"+"+s[3]+"=7")

elif a+b+c-d == 7:
    print(s[0]+"+"+s[1]+"+"+s[2]+"-"+s[3]+"=7")
elif a+b-c+d == 7:
    print(s[0]+"+"+s[1]+"-"+s[2]+"+"+s[3]+"=7")
elif a+b-c-d == 7:
    print(s[0]+"+"+s[1]+"-"+s[2]+"-"+s[3]+"=7")
elif a-b+c+d == 7:
    print(s[0]+"-"+s[1]+"+"+s[2]+"+"+s[3]+"=7")
elif a-b+c-d == 7:
    print(s[0]+"-"+s[1]+"+"+s[2]+"-"+s[3]+"=7")
elif a-b-c+d == 7:
    print(s[0]+"-"+s[1]+"-"+s[2]+"+"+s[3]+"=7")
elif a-b-c-d == 7:
    print(s[0]+"-"+s[1]+"-"+s[2]+"-"+s[3]+"=7")


Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
vector < int > DP(N, 2e9), v(N);
int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> v[i];
    }
    DP[1] = 0;
    for (int i = 2; i <= n; i++) {
      DP[i] = DP[i - 1] + abs(v[i] - v[i - 1]);
      if (i - 2 >= 1) {
        DP[i] = min(DP[i], DP[i - 2] + abs(v[i] - v[i - 2]));
      }
    }
    cout << DP[n] << "\n";
    return 0;
}


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

long long gcd(long long a, long long b)//??相除法求最大公?数
{
	if (b == 0)return a;
	return gcd(b, a%b);
}

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

int main(int argc, char *argv[])
{
	long long a, b;
	while (cin >> a >> b)
	{
		cout << gcd(a, b) << " " << lcm(a, b) << endl;
	}

	return 0;
}

Measured memory_bytes: 3048
N,K,Q = [int(i) for i in input().split()]
A = []
for q in range(Q):
    A.append(int(input()))
from collections import defaultdict as df
cnt = df(int)
for a in A:
    cnt[a] += 1
for n in range(N):
    if K - Q + cnt[n+1] > 0:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 68952
import sys

input = sys.stdin.buffer.readline
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7
saidai = pow(2, n)
dp = [0] * saidai
dp[0] = 1
# dp[i][j] 男i人に対して女の集合Sが合致
bitcnt = [0] * (saidai + 1)
for s in range(saidai):
    # otoko = bin(s).count("1")
    bitcnt[s] = bitcnt[s // 2] + s % 2
    i = bitcnt[s]
    for j in range(n):
        if (s >> j) & 1 == 0:
            if A[i][j] == 1:
                ns = s | 1 << j
                dp[ns] += dp[s]
                dp[ns] %= mod
print(dp[saidai - 1])


Measured memory_bytes: 75228
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    private const int INF = 1000000007;
    private const long INFINITY = 9223372036854775807;
    private struct Pair { public int x, y; }
    public static void Main()
    {
        long X = NextLong();
        long Y = NextLong();
        long Z = NextLong();
        long K = NextLong();
        long[] A = LineLong();
        long[] B = LineLong();
        long[] C = LineLong();
        List<long> AB = new List<long>();
        for (int i = 0; i < X; i++)
            for (int j = 0; j < Y; j++)
                AB.Add(A[i] + B[j]);
        AB.Sort();
        AB.Reverse();
        List<long> _AB = new List<long>();
        for (int i = 0; i < K && i < AB.Count(); i++) _AB.Add(AB[i]);
        List<long> ans = new List<long>();
        foreach (var ab in _AB)
        {
            for (int i = 0; i < Z; i++)
                ans.Add(ab + C[i]);
        }
        ans.Sort();
        ans.Reverse();
        for (int i = 0; i < K; i++)
            Console.WriteLine(ans[i]);
    }
}

public class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static char NextChar() { Confirm(); return char.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}


Measured memory_bytes: 63124
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.141592653589793
using namespace std;



int main() {
//    cout << setprecision(100);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int r;
    cin >> r;
    cout << 3 * r * r;


    




}




Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
inline void prep ()
{
  cin.tie (0);
  cin.sync_with_stdio (0);
};
const double pi = acos(-1.);
//printf(%.12lf\n,mid);
// __builtin_popcount(int) count 1's in binary
// get decimal part of number
/*
double intpart;
double thiss = modf((double)(n*m)/(double)k, &intpart);
*/
// round = (int)(num+.5)
long long mod = 1000000007;
 
// 32 mil = ~1 sec 
long long mymod(long long num){
  if (num< 0 && !(num%mod == 0)){
    if (mod == 1){
      return 0;
    }
    return mod-abs(num)%mod;
  }else{
    return num%mod;
  }
}
 
/*string sentence = And I feel fine...;
    istringstream iss(sentence);
*/  
 
double eps = .000000001;

set<int> axisx;
set<int> axisy;
bool visx[100001] = {false};
bool visy[100001] = {false};
set<int> xs[100001];
set<int> ys[100001];
int cnt = 0;
void dfs(int node, bool which){
    if (which && visy[node] || !which && visx[node]){
        return;
    }
    if (which){
        axisy.insert(node);
        visy[node] = true;
        for (int i : xs[node]){
            dfs(i, !which);
        }
    }else{
        axisx.insert(node);
        visx[node] = true;
        for (int i : ys[node]){
            dfs(i, !which);
        }
    }
}
int main ()
{
  prep();
  int n;
  cin >> n;
  
  set<int> xvals;

  for (int i=0; i<n; i++){
      int a, b;
      cin >> a >> b;
      xs[b].insert(a);
      ys[a].insert(b);
      xvals.insert(a);
  }

  // find L shape
  long long res = 0;

  if (n <= 2){
      cout << 0;
      return 0;
  }
  for (int i : xvals){
      if (visx[i]){
          continue;
      }
      if (ys[i].size() == 0){
          continue;
      }
      axisx.clear();
      axisy.clear();
      cnt = 0;
      dfs(i, false);
      //cout << cnt << " " << axisx.size() << " " << axisy.size() <<  endl;
      for (int j : axisx){
          for (int k : ys[j]){
              if (axisy.count(k)){
                  cnt++;
              }
          }
      }
      res += (long long)axisx.size()*axisy.size()-cnt;
  }
  cout << res;
  return 0; 
}


Measured memory_bytes: 29184
n = gets.to_i
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)

count = 0
n.times do |i|
  # i番目の街
  count += [a[i], b[i]].min

  a[i] -= b[i]
  if a[i] < 0
    b[i] = a[i].abs
  elsif a[i] >= 0
    b[i] = 0
  end
  
  # i+1番目の街
  count += [a[i+1], b[i]].min
  a[i+1] -= b[i]
  if a[i+1] < 0
    a[i+1] = 0
  end
end

puts count

Measured memory_bytes: 19596
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  vector<int>vec(N);
  for(int i=0;i<N;i++){
    cin>>vec.at(i);
  }
  int Light=1;
  bool flag=true;
  int count=0;
  for(int i=0;i<N;i++){
    count=count+1;
    Light=vec.at(Light-1);
    if(Light==2){
      flag=false;
      break;
    }
    else{
    }
  }
  if(flag==false){
    cout<<count<<endl;
  }
  else{
    cout<<-1<<endl;
  }
}
    


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define debug(...) cerr<<__LINE__<<" ["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec)
{ for (auto v : vec) os << v << ' '; os << '\n'; return os; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa)
{ os << '(' << pa.first << ',' << pa.second << ')'; return os; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T)
{ cerr << " " << H; debug_out(T...); }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s.erase(unique(all(s)), s.end());
    cout << s.size() << endl;
}

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


Measured memory_bytes: 3716
#include <iostream>
#include <deque>
#include <utility>
#define llint long long

using namespace std;
typedef pair<llint, llint> P;

struct CHT{
	deque<P> deq;
	
	//assume a1 >= a2 >= a3
	bool check(P p1, P p2, P p3)
	{
		llint a1 = p1.first, b1 = p1.second;
		llint a2 = p2.first, b2 = p2.second;
		llint a3 = p3.first, b3 = p3.second;
		return (a2-a1)*(b3-b2) >= (b2-b1)*(a3-a2);
	}
	llint calc(P p, llint x){
		return p.first * x + p.second;
	}
	
	void add(llint a, llint b){
		P p = make_pair(a, b);
		while(deq.size() >= 2 && check(deq[(int)deq.size()-2], deq[(int)deq.size()-1], p)) deq.pop_back();
		deq.push_back(p);
	}
	llint query(llint x){
		while(deq.size() >= 2 && calc(deq[0], x) >= calc(deq[1], x)) deq.pop_front();
		return calc(deq.front(), x);
	}
};

llint n, c;
llint h[200005];
llint dp[200005];
deque<P> deq;
CHT cht;

int main(void)
{
	cin >> n >> c;
	for(int i = 1; i <= n; i++) cin >> h[i];
	
	cht.add(-2*h[1], h[1]*h[1]);
	for(int i = 2; i <= n; i++){
		dp[i] = cht.query(h[i]) + h[i]*h[i] + c;
		cht.add(-2*h[i], dp[i]+h[i]*h[i]);
	}
	
	cout << dp[n] << endl;
	return 0;
}

Measured memory_bytes: 5632
for i in range(int(input())):
    s, e = map(int, input().split())
    a = []
    if s <= 5:
        if s > e:
            [a.append(i) for i in range(s, e - 1, -1)]
        else:
            [a.append(i) for i in range(s, e + 1)]
    elif s < e:
        [a.append(i) for i in range(s, e + 1)]
    else:
        [a.append(i) for i in range(s, 10)]
        if e <= 5:
            [a.append(i) for i in range(5, e - 1, -1)]
        else:
            [a.append(i) for i in range(5, 0, -1)]
            [a.append(i) for i in range(0, e + 1)]
    print(*a)


Measured memory_bytes: 5596
n,k=map(int,input().split())
l=list(map(int,input().split()))

for i in range(n):
  l[i]=(l[i]+1)/2

lis=[0]*(n+1)
for i in range(n):
  lis[i+1]=lis[i]+l[i]
  
ans=0
for i in range(n-k+1):
  num=lis[i+k]-lis[i]
  ans=max(num,ans)
  
print(ans)

Measured memory_bytes: 32376
# A - Candy Distribution Again

N,x = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
ans = 0

for i in range(N):
    x -= a[i]
    if x<0 or (i==N-1 and x!=0):
        break
    ans += 1

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define x first
#define y second
 
vector<int> ans;
 
int main()
{
	ll targ;
	cin>>targ;
	++targ;
	bool s=0;
	vector<int> key; key.pb(1);
	for(int i=60; 0<=i; --i){
		int b=1&(targ>>i);
		if(!s && b) s=1;
		else if(s){
			if(b) key.pb(1);
			if(i) key.pb(0);
		}
	}
	reverse(all(key));
	int bot=1, top=key.size();
	cout << top*2 << endl;
	for(int i=1; i<=top; ++i) cout << i << ' ';
	for(int x:key){
		if(x == 1) cout << top-- << ' ';
		else cout << bot++ << ' ';
	}
	return 0;
}


Measured memory_bytes: 256
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 1e5 + 10;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << (a - c) * (b - d) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

int main(){
    int n,x;
    cin >> n >> x;
    vector<int>a(n);
    rep(i,n)cin >> a[i];
    int s = 0;
    int c = 1;
    rep(i,n){
        s += a[i];
        if(s<=x){
            c++;
        }
    }
    cout << c << endl;

    return 0;
}

Measured memory_bytes: 888
e1,e2,e3,e4=map(int,input().split())
if e1==e2==e3==e4:
    print('yes')
elif e1==e2 and e3==e4:
    print('yes')
elif e1==e3 and e2==e4:
    print('yes')
elif e1==e4 and e2==e3:
    print('yes')
else:
    print('no')


Measured memory_bytes: 5596
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()

ans = set()
def rec(i, S):
    if S in ans:
        return
    if i == N:
        ans.add(S)
        return
    # 今までに出現した文字は全部追加できる
    for c in S:
        rec(i+1, S+c)
    # 今までに出現した中で最大の文字の次も追加できる
    li = sorted(S)
    rec(i+1, S+chr(ord(li[-1])+1))
rec(1, 'a')
ans = sorted(ans)
[print(s) for s in ans]


Measured memory_bytes: 15872
# -*- coding: utf-8 -*-
import sys

N,*A = map(int, sys.stdin.buffer.read().split())

S = [0 for _ in range(10**6+1)]
T = [0 for _ in range(10**6+1)]

for a in A:
  S[a] += 1

count = 0
for i in range(1,10**6+1):
  if T[i] == 1:
    continue
  if S[i] == 0:
    continue
  if S[i] == 1:
    count += 1
  for j in range(10**6//i+1):
    T[i*j] = 1

print(count)

Measured memory_bytes: 219812
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)

template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl
#define MOD 1000000007


//ここから編集する
class Solve {
public:
    ll A, B, C, X, Y;

    void input() {
        cin >> A >> B >> C >> X >> Y;

    }

    void solve() {
        input();
        if (A > B) {
            swap(A, B);
            swap(X, Y);
        }

        // A <= B
        ll ans = 0ll;
        if (A + B >= 2 * C) {
            ll dec = min(X, Y);
            ll cost = 2 * C * dec;
            ans += cost;
            X -= dec;
            Y -= dec;
        }

        //A,Xの処理
        if (X > 0) {
            if (2 * C > A) {
                ll dec = X;
                ll cost = A * dec;
                ans += cost;
                X -= dec;
            } else {
                ll dec = X;
                ll cost = 2 * C * dec;
                ans += cost;
                X -= dec;
                Y -= dec;
            }
        }

        if (Y > 0) {
            if (2 * C > B) {
                ll dec = Y;
                ll cost = B * dec;
                ans += cost;
                Y -= dec;
            } else {
                ll dec = Y;
                ll cost = 2 * C * dec;
                ans += cost;
                X -= dec;
                Y -= dec;
            }
        }

        cout << ans << endl;

    }
};


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

    Solve().solve();


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define maxn 100005
#define mod 1000000007
typedef pair<int,int> pii;
typedef map<int,int> mii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<long long> vll;
typedef vector<bool> vb;
typedef set<int> si; 
#define fori(i,a,b) for(int i = (a); i < (b); ++i)
#define rep(i,b,a) for(int i = (b); i >= (a); --i)
#define all(a) (a).begin(), (a).end()
#define __builtin_popcountll bitCountLL
#define __builtin_popcount bitCount
//__builtin_ctz 末尾0的个数, __builtin_clz 前导0的个数
//__builtin_ffs 最后一个1的位置
const int INF = 2e9;
const ll ML = 4e18;

ll solve() {
	int n, k;
	 cin >> n >> k;
	vll a,b;
	for(int i = 0; i < n ;++i) {
		ll x;
		cin >> x ;
		if(x >= 0) a.push_back(x);
		else b.push_back(x);
	}
	sort(a.rbegin(),a.rend());
	sort(b.begin(),b.end());
	ll res = 1;
	if(a.size() == 0 && k % 2) {
		int i = b.size() -1;
		while(k--) {
			res = (res * b[i--]) % mod;
		}
		res = (res + mod) % mod;
		return res;
	}
	if((int)(a.size() + b.size()) == k) {
		for(ll i : a) res = (res * i) % mod;
		for(ll i : b) res = (res * i) % mod;
		res = (res + mod) % mod;
		return res;
	}
	bool ok = false;
	int pos = a.size() - 1;
	for(int i = 0; i * 2 <= (int) b.size();i++) {
		if(2*i + (int)a.size() < k) continue;
		if(!ok) {
			ok = true;
			pos =  k - 1 - 2 * i;
			continue;
		}
      if(pos < 1) break;
		if(a[pos ] * a[pos - 1] > b[2 * i - 1] * b[2 * i - 2]) 
			break;
		pos -= 2;
	}
	for(int i = 0; i <= pos; i++) res = (res * a[i]) % mod;
	int len = k - pos  - 1;
	for(int i = 0; i < len /2; i++) {
		ll x = (b[2 * i] * b[2 * i + 1]) % mod;
		res =  (res * x ) % mod;
	}
	return res;
}


int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
	//cout.precision(30); cout << fixed;
	//freopen("D:\\data_in.txt", "r", stdin);
   cout << solve() << endl;
   // cout << (-1) % 3 << endl;
    /*clock_t start,finish;
    start = clock();
   
    finish = clock();
    cout << "\n" << (double)(finish - start) / (double)(CLOCKS_PER_SEC) * 1000 << "ms" << endl;
    */
    return 0;
}

/***************************************************************
 question:
 idea:
 tag:
 record:
 ***************************************************************/


Measured memory_bytes: 5632
#include<stdio.h>
#define MAX 10000
#define NIL -1

struct Node{
  int p,l,r;
};

struct Node T[MAX];
int n;

void preParse(int u){
  if(u == NIL)return;
  printf(" %d",u);
  preParse(T[u].l);
  preParse(T[u].r);
}
void inParse(int u){
  if(u == NIL)return;
  inParse(T[u].l);
  printf(" %d", u);
  inParse(T[u].r);
}
void postParse(int u){
  if(u == NIL)return;
  postParse(T[u].l);
  postParse(T[u].r);
  printf(" %d",u);
}

int main(){
  int v,l,r,root,i;
  scanf("%d", &n);
  for (i = 0; i < n; i++){
    T[i].p = NIL;
  }

  for(i = 0;i < n;i++){
    scanf("%d %d %d",&v,&l,&r);
    T[v].l = l;
    T[v].r = r;
    if(l != NIL)T[l].p = v;
    if(r != NIL)T[r].p = v;
  }

  for(i = 0;i < n;i++)if(T[i].p == NIL)root = i;
  printf("Preorder\n");
  preParse(root);
  printf("\n");
  printf("Inorder\n");
  inParse(root);
  printf("\n");
  printf("Postorder\n");
  postParse(root);
  printf("\n");
}



Measured memory_bytes: 2088
#include <stdio.h>
#include <string.h>

int main(){
   char str_s[128], str_p[128];
   int i, j, c, n, m;
   scanf("%s",str_s);
   scanf("%s",str_p);
   n=strlen(str_s);
   m=strlen(str_p);
   for(i=0;i < n;i++){
      c=0;
      for(j=0;j < m;j++){
         if(i+j <= n-1){
            if(str_s[i+j] !=str_p[j]){
               break;
            }
         }else{
            if(str_s[i+j-n] !=str_p[j]){
               break;
            }
         }
      }
      if(j == m){
         printf("Yes\n");
         c=1;
         break;
      }
   }
   if(c == 0){
      printf("No\n");
   }

   return 0;
}

Measured memory_bytes: 2676
#include<bits/stdc++.h>
#define ll long long
#define fr(i,x) for( int i=0;i<(x);i++)
#define io ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
double calcAngle(ll h, ll m);
double calcAngle(ll h, ll m)
{
    if(h==12) h=0;
    if(m==60) m=0;
    double hour=0.5*(h*60+m);
    double minute=(6*m);
    double angle =abs(hour-minute);
    angle = min(360 -angle,angle);
    return angle;
}
int main() 
{ 
      ll a,b,h,m;
      cin>>a>>b>>h>>m;
       
      cin>>a>>b>>h>>m;
      double ang=calcAngle(h,m);
      double axy=cos(3.141592653589793238*ang/180);
      double ams=pow(a,2)+pow(b,2)-(2*a*b*axy);
      cout<<fixed<<setprecision(30)<<sqrt(ams)<<endl;
       return 0;
       
}

Measured memory_bytes: 4188
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

using namespace std;


int main() {
  int x;
  cin >> x;
  cout << x * x * x << endl;
  return 0;
};


Measured memory_bytes: 256
#include <iostream> 
#include <vector>
#include <cmath>
#include <string>
#include <sstream>
#include <algorithm>
#include <queue>
#include <stack>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <map>
#include <iomanip>
#include <cctype>
#include <climits>
 
using namespace std;
 
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
 
using ll = long long int;
 
#define mp(a,b) make_pair(a,b)
 
const int MOD = 1000 * 1000 * 1000 + 7;
 
 
 
vi v = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };
 
int main() {
 
	int k;
	cin >> k;
 
	cout << v[k - 1] << '\n';
 
	return 0;
}

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

void init()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
}

int main()
{
    init();
    int h, w, k;
    cin>>h>>w>>k;
    vector<vector<char>>c(h,vector<char>(w));
    rep(i,h){
        rep(j,w){
            cin>>c[i][j];
        }
    }
    int num;
    int ans=0;
    rep(i,(1<<h)){
        bitset<6>hs(i);
        rep(j,(1<<w)){
            bitset<6>ws(j);
            num=0;
            rep(k,h){
                rep(l,w){
                    if(hs.test(k)!=true && ws.test(l)!=true){
                        if(c[k][l]=='#')num++;
                    }
                }
            }
            if(num==k)ans++;
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3612
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
#include <map>
#include <string>
#include <math.h>
using namespace std;
typedef long long ll;


int main() {

    int N;
    cin >> N;
    int a[N];
    for(int i=0;i<N;i++){
        cin >> a[i];
    }

    int map[7]={0};

    int other = 0;
    for(int i=0;i<N;i++){
        if(a[i]>=3200){
            other++;
        }else{
            map[a[i]/400]++;
        }
    }
    int min=0;
    for(int i=0;i<8;i++){
        if(map[i]!=0){
            min++;
        }
    }
    if(min==0&&other>0){
        cout << 1 << " " << other << endl;
    }else{
        cout << min << " " << min + other <<endl;
    }
    

    return 0;
}

Measured memory_bytes: 256
A,B,C,D = map(int,input().split())

Takahasi = [A,B]
Aoki = [C,D]

while Aoki[0] > 0 and Takahasi[0] > 0:
    
    n = Aoki[0] - Takahasi[1]
    Aoki[0] = n
    
    if Aoki[0] <= 0:
        print("Yes")
        break    
    
    i = Takahasi[0] - Aoki[1]
    Takahasi[0] = i
    
    if Takahasi[0] <= 0:
        print("No")
        break

Measured memory_bytes: 9196
#include <string>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<bool> isAC(n + 1);
    vector<int> WAnum(n+1);
    rep(i, n+1){
        isAC[i] = false;
        WAnum[i] = 0;
    }
    int WAtot = 0, ACtot = 0;
    rep(i, m){
        int p;
        string s;
        cin >> p >> s;
        if(!isAC[p]){
            if(s == "WA"){
                WAnum[p]++;
            }else if (s == "AC"){
                ACtot++;
                WAtot += WAnum[p];
                isAC[p] = true;
            }
        }
    }
    cout << ACtot << " " << WAtot << endl;
}

Measured memory_bytes: 640