akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include<bits/stdc++.h>
#include<map>
#include<iostream>
#include<cmath>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;


int main(){
   ll K,N;
   cin >> K >> N;
   vector<ll> A(N);
   rep(i,N){
      cin >> A[i];
   }
   vector<ll> B(N);
   B[N - 1] = A[0] + (K - A[N - 1]);
   rep(i,N - 1){
      B[i] += abs(A[(i + 1)] - A[i]);
   }
   sort(B.begin(), B.end());
   ll ans = 0;
   rep(i,N-1){
      ans += B[i];
   }
   cout << ans << endl;
}

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

int main(){
	int s[101][101] = {0};
	int i, j, r, c;
	
	cin >> r >> c; 
	
	for(i = 0; i < r; i++){
		for(j = 0; j < c; j++){
			cin >> s[i][j];
			s[i][c] += s[i][j];
			s[r][j] += s[i][j];
		}
		s[r][c] += s[i][c];
	}
	
	for(i = 0; i < r + 1; i++){
		for(j = 0; j < c + 1; j++){
			cout << s[i][j];;
			if(j != c){
				cout << " ";
			}
		}
		cout << endl;
	}
	
	return 0;	
}

Measured memory_bytes: 3128
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using vs=vector<string>;
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF    	((ll)1ll<<60)
#define INF     	((int)1<<30)
#define EPS     	(1e-9)
#define MOD     	(1000000007ll)
#define fcout(a)	cout<<setprecision(a)<<fixed
#define fs 			first
#define sc			second
#define PI			3.1415926535897932384

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s; a=0;} return os;}
template<class T> void chmax(T &a, const T &b){if(a<b)a=b;}
template<class T> void chmin(T &a, const T &b){if(a>b)a=b;}
void YN(bool b){cout<<(b?"YES":"NO")<<endl;}
void Yn(bool b){cout<<(b?"Yes":"No")<<endl;}
void yn(bool b){cout<<(b?"yes":"no")<<endl;}

const int N=3001;
ll dp[3001][3001];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin>>n;
	vl v(n);
	rep(i,n)cin>>v[i];
	//rep(i,N)rep(j,N)dp[i][j]=pn*((j-i)%2==0?-LINF:LINF);
	int pn=(n%2==1?1:-1);
	rep(i,n){
		for(int j=0;j+i<n;j++){
			if(i==0){
				dp[j][j]=pn*v[j];
			}
			else if((n-i)%2==1){
				//max
				dp[j][j+i]=max(dp[j+1][j+i]+v[j],dp[j][j+i-1]+v[j+i]);
			}
			else {
				dp[j][j+i]=min(dp[j+1][j+i]-v[j],dp[j][j+i-1]-v[j+i]);
			}
		}
	}
	cout<<dp[0][n-1]<<endl;
}

Measured memory_bytes: 70144
#include <bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#define invrep(i,n) for(int64_t i=n-1;i >= 0;i--)
using namespace std;

//////全探索したいときに開けよ////////
vector<vector<int>> fspattern;
vector<int> fspattern_draft;
int fspcnt = 0;

void setfspattern_core(int floor,int number,int degree){
  if(floor==degree){
    fspattern.at(fspcnt) = fspattern_draft;
    fspcnt++;
  }else{
    rep(i,number){
      fspattern_draft.at(floor) = i;
      setfspattern_core(floor+1,number,degree);
    }
  }
}

void setfspattern(int number,int degree){
  fspcnt = 0;
  int64_t array_num = 1;
  rep(i,degree){
    array_num *= number;
  }
  fspattern = vector<vector<int>>(array_num,vector<int>(degree));
  fspattern_draft = vector<int>(degree);
  setfspattern_core(0,number,degree);
}

//////nCrのmodを求めたいときに開けよ/////////
//int64_t univMod = 1000000007;
//int64_t factnum = 100000
//vector<int64_t> modfact(factnum);
//vector<int64_t> modinvfact(factnum);

/*void setmodfact(){
  for(int i=0;i<factnum;i++){
    if(i == 0){
      modfact.at(i) = 1;
    }else{
      modfact.at(i) = (modfact.at(i-1)*i)%univMod;
    }
  }
}

int64_t calcmodpower(int64_t a,int64_t n){
  int64_t res = 1;
  while(n != 0){
    if(n & 1){
      res = (res * a) % univMod;
    }
    a = (a*a) % univMod;
    n = n >> 1;
  }
  return res;
}

int64_t calcinverse(int64_t n){
	return calcmodpower(n,univMod-2);
}

void setmodinvfact(){
  for(int i=0;i<factnum;i++){
    if(i==0){
      modinvfact.at(i) = 1;
    }else{
      modinvfact.at(i) = calcmodpower(modfact.at(i),univMod-2);
    }
  }
}*/


/*
int64_t calcGCD(int64_t a,int64_t b){
	int64_t p = a;
	int64_t q = b;
	int64_t c = a%b;
	while(c != 0){
		p = q;
		q = c;
		c = p%q;
	}
	return q;
}
*/

int main(){
  string s1,s2,u;
  int n1,n2;
  cin >> s1 >> s2 >> n1 >> n2 >> u;
  if(s1 == u){
    printf("%d %d\n",n1-1,n2);
  }else{
    printf("%d %d\n",n1,n2-1);
  }
    
}
        
    
      
    
      
  
  

Measured memory_bytes: 256
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char c = sc.next().charAt(0);
		switch (c) {
		case 'a':
		case 'e':
		case 'i':
		case 'o':
		case 'u':
			System.out.println("vowel");
			break;
		default:
			System.out.println("consonant");
			break;
		}
		
		sc.close();
	}
}



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

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

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if(a + b > c + d)
    {
        cout << "Left\n";
    }
    else if(a + b < c + d)
    {
        cout << "Right\n";
    }
    else
    {
        cout << "Balanced\n";
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

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

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int i,j,k,x,y;
        for(i=0;;i++){
            x=sc.nextInt();
            y=sc.nextInt();
            if((x==0)&&(y==0)){
                break;
            }
            for(j=0;j<x;j++){
                if(j==0 || j==x-1){
                    for(k=0;k<y;k++){
                        System.out.print("#");
                    }
                    System.out.print("\n");
                }
                else{
                    System.out.print("#");
                    for(k=0;k<y-2;k++){
                        System.out.print(".");
                    }
                    System.out.print("#\n");
                }
            }
            System.out.print("\n");
        }
    }
}


Measured memory_bytes: 36840
import java.util.Scanner;

public class Main{
    public static void main(String[] arg){
        int h, m, s, ss;
        h = 0;
        m = 0;
        s = 0;
        Scanner scan = new Scanner(System.in);
        ss  = scan.nextInt();
        if(ss >= 60){
            m = ss / 60;
            s = ss % 60;
            if(m >= 60){
                h = m / 60;
                m = m % 60;
            }
        }
        System.out.println(h +":"+ m +":"+ s);
    }
}


Measured memory_bytes: 26188
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> a(q),b(q),c(q),d(q);
    for (int i = 0; i < q; i++) {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        a[i]--;
        b[i]--;
    }
    int ans=0;
    vector<int> perm(m+n-1,1);
    for(int i = 0; i < m-1; i++){
        perm[i]=0;
    }

    do{
        vector<int> box;
        int sum=0;
        int zerocnt=1;
        for(int i = 0; i < m+n-1; i++){
            if(perm[i]==0) zerocnt++;
            else box.push_back(zerocnt);
        }
        for(int i = 0; i < q; i++){
            if(box[b[i]]-box[a[i]]==c[i]) sum+=d[i];
        }

        ans=max(ans,sum);
    }while(next_permutation(perm.begin(), perm.end()));

    cout<<ans<<endl;
}

Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n , a , b ; cin >> n >> a >> b ;
    string str ; cin >> str ;
    int total = a+b;
    for(int i = 0 ; i < str.length();i++)   
    {
        if(str[i]=='c') cout << "No" << endl;
        if(str[i]=='a')
        {
            if(total>0) 
            {
                cout <<"Yes" << endl;
                total--;
            }
            else cout << "No" << endl;
        }
        if(str[i]=='b') 
        {
            if(total>0)
            {
                if(b>0)
                {
                    cout <<"Yes" << endl;
                    total--;
                    b--;
                }
                else
                {
                    cout << "No" << endl;
                }
            }
            else cout << "No" << endl;
        }
    }
    return 0 ;
}

Measured memory_bytes: 3768
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = sum(b)
tmp = 21
for i in a:
    if i - tmp == 1:
        ans += c[tmp - 1]
    tmp = i
print(ans)

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


int main(){
    string s;
    cin >> s;
    int x = s.size(), cnt = 0, large = 0;
    for (int i = 0; i < x;i++){
        if(s.at(i)-'a'<0)
            large++;
    }

    if (s.at(0) == 'A'&&s.at(x-1)!='C'){
        for (int i = 2; i < x-1; i++){
            if (s.at(i) == 'C')
                cnt++;
        }
        if(cnt==1&&large==2){
            cout << "AC" << endl;
            return 0;
        }
    }
    cout << "WA" << endl;

    return 0;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

// 約数の全列挙
vector<ll> divisor(ll n) {
  vector<ll> ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int main()
{
    cout << fixed << setprecision(15);

    ll A, B, K;

    cin >> A >> B >> K;
    vector<ll> P = divisor(gcd(A, B));

    cout << P[P.size()-K] << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#define LEN 100005

typedef struct pp{
char name[100];
int t;
}P;
int head,tail,n;
P Q[LEN];

void enqueue(P x){
Q[tail]=x;
tail=(tail+1)%LEN;
}

P dequeue(){
P x=Q[head];
head=(head+1)%LEN;
return x;
}

int min(int a,int b){return a<b?a:b;}

int main(){
int elaps =0,c;
P u;
int i,q;

  scanf("%d %d", &n,&q);
  for (int i = 1; i <= n; i++ ){
scanf("%s",Q[i].name);
scanf("%d",&Q[i].t);
  }
  head=1;tail =n+1;
  while( head != tail ){
  u=dequeue();
  c=min(q,u.t);
  u.t -= c;
  elaps+=c;
  if(u.t>0)enqueue(u);
  else{
  printf("%s %d\n",u.name,elaps);
   }
  }
  return 0;
}

Measured memory_bytes: 12832
import java.math.BigDecimal;
import java.util.Scanner;

public class Main {

	public static void main(String args[]) {
		 Scanner scan = new Scanner(System.in);
	     String str = scan.nextLine();
	     String[] chars = str.split(" ");
	     BigDecimal a= BigDecimal.valueOf(Long.valueOf(chars[0]));
	     BigDecimal b= BigDecimal.valueOf(Long.valueOf(chars[1]));
	     BigDecimal x= BigDecimal.valueOf(Long.valueOf(chars[2]));

	     BigDecimal value = a.multiply(a.multiply(b));
	     if(value.compareTo(x.multiply(new BigDecimal("2.00")))>0) {
	    	 BigDecimal tri = x.divide(a,12, BigDecimal.ROUND_HALF_UP);
	    	 BigDecimal tan = tri.multiply(new BigDecimal("2.00")).divide(b ,12, BigDecimal.ROUND_HALF_UP).divide(b ,12, BigDecimal.ROUND_HALF_UP);
	    	 System.out.println(90-Math.atan(tan.doubleValue())*180/Math.PI);
	     }
	     else {
	    	 BigDecimal tri = ((a.multiply(a.multiply(b))).subtract(x)).divide(a,12, BigDecimal.ROUND_HALF_UP);
	    	 BigDecimal tan = tri.multiply(new BigDecimal("2.00")).divide(a ,12, BigDecimal.ROUND_HALF_UP).divide(a ,12, BigDecimal.ROUND_HALF_UP);
	    	 System.out.println(Math.atan(tan.doubleValue())*180/Math.PI);
	     }
	}

}


Measured memory_bytes: 24916
n,m=map(int,input().split())
a=[list(input()) for i in range(n)]
b=[list(input()) for i in range(m)]

for i in range(n-m+1):
  for j in range(n-m+1):
    #ここで左上の位置を固定。
    #この配置について、「m*mが全てこの位置のaに一致するか」を調べる。
    flag=True
    for k in range(m):
      for l in range(m):
        if a[i+k][j+l]!=b[k][l]:
          flag=False
          break
      if flag==False:
        break
    if flag:
      print("Yes")
      exit()
        #一致しない場合は、この配置についての確認を終えるため、2段目のfor文に戻りたい…
print("No")

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

typedef long long ll;
typedef pair<int,int> pii;

long long MOD = 10000000000 + 7;

int main(){
  cout << setprecision(10);
  int H,W; cin >> H >> W;
  int diff[H][W];
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> diff[i][j];
    }
  }
  int MAX = 0;
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      int tmp; cin >> tmp;
      diff[i][j] = abs(diff[i][j] - tmp);
      MAX = max(MAX, diff[i][j]);
    }
  }

  MAX = MAX * (H + W) + 10;

  vector<vector<vector<bool>>> dp(H, vector<vector<bool>>(W, vector<bool>(MAX, false)));

  dp[0][0][diff[0][0]] = true;
  cerr << diff[0][0] << endl;

  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      for(int k = 0; k < MAX; k++){
        if(dp[i][j][k]){
          if(i+1<H){
            dp[i+1][j][k + diff[i+1][j]] = true;
            dp[i+1][j][abs(k - diff[i+1][j])] = true;
          }
          if(j+1<W){
            dp[i][j+1][k + diff[i][j+1]] = true;
            dp[i][j+1][abs(k - diff[i][j+1])] = true;
          }
        }
      }
    }
  }

  for(int k = 0; k < MAX; k++){
    if(dp[H-1][W-1][k]){
      cout << k << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 13788
#include<stdio.h>


typedef struct node{  
  int parent;
  int right;
  int left;


} tree1;



tree1 A[1000000];
int number;
int D[1000000];

int H[1000000];


void depth(int i,int p){


  if(i==-1) return;
  D[i]=p;
  depth(A[i].left,p+1);
  depth(A[i].right,p+1);
}


int height(int u){

  int h=0,j=0;


  if(A[u].left!=-1){
    h=height(A[u].left)+1;}

  if(A[u].right!=-1){
    j=height(A[u].right)+1;}

  return H[u]=(h>j?h:j);


}



int sibling(int i){

  if(A[i].parent==-1){return -1;}
  if(A[A[i].parent].left != i && A[A[i].parent].left !=-1){return A[A[i].parent].left;}
  
  if(A[A[i].parent].right != i && A[A[i].parent].right !=-1){return A[A[i].parent].right;}
  

  return -1; 
  }


  








int main(){



  
  scanf("%d",&number);
  

  int i,j;

  

  for(i=0;i<number;i++){
    

    A[i].parent=A[i].right=A[i].left=-1;
  }


  

  int a,r1,r2;
  int root=0;
  //子の値を貰っていく
  for(i=0;i<number;i++){
    scanf("%d%d%d",&a,&r1,&r2);
      
  A[a].left=r1;
  A[a].right=r2;

  if(r1!=-1)A[r1].parent=a;
  if(r2!=-1)A[r2].parent=a;

  }
  
    
    
   
  
  
  for(i=0 ; i<number ; i++){
    if(A[i].parent==-1){root=i;}
  }



  depth(root,0);
  height(root);
  
  
  int deg=0;
  /*出力*/
  for(i=0;i<number;i++){
    deg=0;
    printf("node %d: parent = %d, sibling = %d,",i,A[i].parent,sibling(i));
    
    if(A[i].left !=-1)deg++;
    if(A[i].right !=-1)deg++;



    printf(" degree = %d, depth = %d, height = %d,",deg,D[i],H[i]);




    
    if(A[i].parent==-1){printf(" root\n");}
    else if(A[i].left==-1 && A[i].right == -1){printf(" leaf\n");}
    else {printf(" internal node\n");}

  

  }

  
  return 0;
}




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

#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    bool appear[1000] = {};
    int X, N; cin >> X >> N;
    rep(i, N){
        int a; cin >> a; appear[a] = true;
    }
    int ans = 0;
    for(int i = 1; i < 1000; i++){
        if(appear[i]) continue;
        if(abs(ans-X) > abs(i-X)) ans = i;
    }
    cout << ans << endl;
    return 0;
}

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

int main()
{
	int r, g, b; cin >> r >> g >> b;

	int tmp = 100 * r + 10 * g + b;

	string ans = "NO";

	if (tmp % 4 == 0) ans = "YES";
		
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
N,M,x,y=map(int,input().split())
X=list(map(int,input().split()))
Y=list(map(int,input().split()))
if x<y:
    X.append(x)
    Y.append(y)
    X.sort()
    Y.sort()
    if X[-1]<Y[0]:
        print('No War')
    else:
        print('War')
else:
    print('War')

Measured memory_bytes: 38384
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

const int N = 5e4 + 5;

int n,m,q,mod,s,t,r,u[N],v[N],c[N],g,fa[N * 6] , id[N][2][3] , icnt;
bool can[2][1000100];

int get(int x) {
	if (fa[x] != x) {
		return fa[x] = get(fa[x]);
	}
	return fa[x];
}

void link(int x,int y) {
	x = get(x) , y = get(y);
	if (x != y) {
		fa[x] = y;
	}
}
int main() {
	scanf("%d%d%d%d",&n,&m,&q,&mod);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d",&u[i],&v[i],&c[i]);
		g=__gcd(g,abs(c[i]-c[1]));
	}
	if (!g) g=mod;
	mod=__gcd(mod,3*g);
	int z=c[1]%g;

	for (int i = 1; i <= n; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 3; k++)
				id[i][j][k] = ++icnt;

	for (int i = 1; i <= icnt; i++) fa[i]=i;
	for (int i = 1; i <= m; i++) {
		int w=(c[i]-z)/g;
		for (int p = 0; p < 2; p++)
			for (int q = 0; q < 3; q++) {
				link(id[u[i]][p][q],id[v[i]][1^p][(2*q+w)%3]);
				link(id[v[i]][p][q],id[u[i]][1^p][(2*q+w)%3]);
			}
	}

	int mul = z;
	for (int i = 0; i <= (mod << 1); i++) {
		can[i & 1][mul] = 1;
		mul = 2 * mul % mod;
	}

	while (q--) {
		scanf("%d%d%d",&s,&t,&r);
		int ret=0;

		for(int p = 0; p < 2; p++)
			for(int q = 0; q < 3; q++)  
			if (get(id[t][0][0])==get(id[s][p][q])) {
				ret|=can[p][(r+z+(3-q)*g)%mod];
				if (ret) break;
			}
		puts(ret?"YES":"NO");
	}
	return 0;
}

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

using namespace std;

#define FOR(i, n) for(int i = 0; i < (int) n; i++)
#define rall(v) v.rbegin(), v.rend()
#define all(v) v.begin(), v.end()
#define PB push_back
#define F first
#define S second

typedef unsigned long long llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;

const int INF = 1e9+10;
const ll MOD = 1e9+7;

void solve(){
	int n, k, c; cin >> n >> k >> c;
	string s; cin >> s;

	bitset<200007> to(0), from(0);
	bool ok = true;
	int aux = 0;
	for(int i = 0; i < n; i++){
		if(!ok) aux++;
		else if(ok && s[i] == 'o'){
			to[i] = 1;
			ok = false;
		}
		if(aux == c){
			ok = true;
			aux = 0;
		}
	}
	aux = 0;
	ok = true;
	for(int i = n-1; i >= 0; i--){
		if(!ok) aux++;
		else if(ok && s[i] == 'o'){
			from[i] = 1;
			ok = false;
		}
		if(aux == c){
			ok = true;
			aux = 0;
		}
	}

	if((int)(to&from).count() > k){
		return;
	}

	FOR(i, n)
		if(to[i] && from[i])
			cout << i+1 << '\n';

}

int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	
	int t=1; //cin >> t;
	while(t--){
		solve();
	}

	return 0;
}

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

using namespace std;

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

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

int N;
vector<int> a;
int main() {
    cin >> N;
    a.resize(N);
    rep(i, N) cin >> a[i];
    rep(i, N) a[i]--;

    long long ans = 0;

    rep(i, N) {
        if (i == a[a[i]]) ans++;
    }
    cout << ans / 2 << endl;

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tii;
#define rep(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

int main(){
  int N; cin >> N;
  string s; cin >> s;
  int cnt = 0;
  for(int i=0;i<N;i++){
    if(s[i]=='R') cnt++;
  }
  int ans = 0;
  for(int i=0;i<cnt;i++){
    if(s[i]=='W') ans++;
  }
  cout << ans << endl;
 
}


Measured memory_bytes: 3732
import java.util.Scanner;

/**
 * @author shengboxu
 */

public class Main {
    public static void main(String [] args)
    {
        Scanner sc = new Scanner(System.in);
        final int N = sc.nextInt();
        final int[] A = new int[N];
        
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }
        
        int ans = A[0];
        
        for (int i = 0; i < N; i++) {
            final Numeric numeric = new Numeric(ans, A[i]);
            ans = numeric.getGcd();
        }
        
        System.out.println(ans);
    }
    
    public static class Numeric {
        private int a;
        private int b;
        
        public Numeric(final int a, final int b) {
            this.a = a < b ? a : b;
            this.b = (a + b) - this.a;
        }
        
        public int getGcd() {
            int tmp;
            while ((tmp = a % b) != 0) {
                a = b;
                b = tmp;
            }
            return b;
        }
    }
}

Measured memory_bytes: 52596
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
using namespace std;
const long long int INF = 1e18;
const long long int mod = 1e9+7;
typedef pair<ll,ll> pairs;
vector<pairs> p;


ll gcd(ll A,ll B){
    if (A%B==0)return(B);
    else return(gcd(B,A%B));
}

ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

vector<vector<ll>> combination(ll n, ll r){
    vector<vector<ll>> v(n + 1, vector<ll>(n + 1, 0));
    for(ll i=0;i<v.size();++i){
        v[i][0] = 1;
        v[i][i] = 1;
    }
    for(ll i=1;i<v.size();++i){
        for(ll j=0;j<i;++j){
            v[i][j] = (v[i - 1][j - 1] + v[i - 1][j]);
        }
    }
    return v;
}

bool kai(string S){
    bool flag = true;
    for(ll i=0;i<S.size()/2;++i){
        if(S[i] != S[S.size()-i-1]){
            flag = false;
            break;
        }
    }
    return flag;
}
// ------------------------------------

int main(){
    ll n;
    cin>>n;
    vector<ll> a(n);
    vector<ll> b(n+1);
    b[0] = 0;
    for(ll i=0;i<n;++i){
        cin>>a[i];
        b[i+1] = a[i] + b[i];
    }
    ll ans = INF;
    for(ll i=0;i<n;++i){
        ans = min(ans, abs(2*b[i]-b[n]));
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 3328
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define cool ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int  long long int
#define pb push_back
#define fe first
#define lb lower_bound 
#define ub upper_bound
#define pii pair<pair<int,int>,pair<int,int> >
#define se second
#define endl "\n"
#define pi pair<int, int>
#define mi          map<int,int>
#define mii         map<pi,int>
#define vi vector<int> 
#define vvi vector<vi>
#define bs   binary_search
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,a,b) for(int i=a;i<=b;i++)	
#define all(c) (c).begin(),(c).end()
#define sz(x)       (int)x.size() 
#define PI 3.14159265358979323846

 const int N=1e2+5;

 int mod= 1e9+7;
 int dx[4]={0,0,+1,-1};
 int dy[4]={+1,-1,0,0};  
 
 
int po(int a, int b) {
	a %= mod;
	int res = 1;
	while (b > 0) {
		if (b & 1)
			res = (res * a) % mod;
		a =(a*a) % mod;
		b >>= 1;
	}
	 return res;	
  }


void solve() {
       int n,k;
       cin>>n>>k;
       vi dp(n,0);
       rep(i,0,n) cin>>dp[i];
       rep(i,1,n) 
         dp[i]+=dp[i-1]; 
       int ans=0;
       rep(i,k-1,n) {
		      ans=max(ans,dp[i]-(i-k>=0?dp[i-k]:0));
		   }       
	  double sol=(double)(ans+k)/2.0;
	  cout<<fixed<<setprecision(6)<<sol<<endl;	         
}

    
int32_t main() {
	cool;
	int t=1;	

	//cin>>t;
	while(t--)
	  solve();

  return 0;	   
}


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

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

    long long a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;

    long long l, m, n;
    
    l = a * x + b * y;
    
    long long maxi = max(x, y), mini = min(x, y);
    m = 2 * c * mini;
    m += (maxi - mini) * (mini == x ? b : a);

    n = c * 2 * maxi;

    cout << min(l, min(m, n)) << endl;

    return 0;
}

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

int main(){
  int a, b, N;
  cin >> a >> b >> N;
  int M = 1e3+10;
  vector<int> A(M);
  for(int i = 0; i < N; ++i){
    int s, f;
    cin >> s >> f;
    ++A[s];
    --A[f];
  }
  for(int i = 0; i < M-1; ++i)
    A[i+1] += A[i];
  for(int i = a; i < b; ++i){
    if(A[i] > 0){
      cout << 1 << endl;
      return 0;
    }
  }
  cout << 0 << endl;
}



Measured memory_bytes: 3120
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PI pair<int,int>
#define ff first
#define ss second
#define MAX 111111
#define endl '\n'
#define boost ios_base::sync_with_stdio(0);cin.tie(0)
#define INF LONG_MAX
const int MOD=1e9+7;

int mod(int n)
{
	while(n<MOD)
		n+=MOD;
	return n%MOD;
}

int32_t main()
{
    boost;
    int n;
    cin>>n;
    vector<PI>ve[n+1];
    for(int i=0;i<n;i++)
    {
    	int m,u,v;
    	cin>>m;
    	while(m--)
    	{
    		cin>>u>>v;
    		ve[i].push_back({u,v});
    	}
    }

    int ans=0;
    for(int i=1;i<(1ll<<n);i++)
    {
    	int a[n+1]={0};
    	int c=0;
    	for(int j=0;j<n;j++)
    	{
    		if(i&(1ll<<j))
    		{
    			c++;
    			a[j]=1;
    		}
    	}

    	int f=0;
    	for(int j=0;j<n;j++)
    	{
    		if(a[j]==1)
    		{
    			for(auto p:ve[j])
    			{
    				if((a[p.ff-1]==1 && p.ss==0) or(a[p.ff-1]==0 && p.ss==1))
    				{
    					f=1;
    					break;
    				}
    			}
    		}
    	}
    	if(f==0){
    		ans=max(ans,c);
    	}
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
inputnums = input().split()                                                                   
x = int(inputnums[0])
y = int(inputnums[1])
inputstr=[]
for i in range(x):
        inputstr.append(input())
pixel=[]
pixel.append("#"*(len(inputstr[-1])+2))
for i in range(x):
        pixel.append("#"+inputstr[i]+"#")


pixel.append("#"*len(pixel[-1]))
output=""
for i in range(len(pixel)):
    output+=pixel[i]+"\n"

print(output)


Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<tuple>
#include<sstream>
#include<math.h>
#define rep(i,n) for(int i =0;i<(int)(n);i++)
typedef long long ll;
using namespace std;
int main() {
	int r;
	cin >> r;
	cout << r * r << endl;
	return 0;
}


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

int main() {
    int64_t A, B, C, K;
    cin >> A >> B >> C >> K;

    while (K) {
        if (A >= B) {
            B *= 2;
        } else if (B >= C) {
            C *= 2;
        }
        K--;
    }

    cout << (A < B && B < C ? "Yes" : "No") << endl;
}

Measured memory_bytes: 3632
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#endif
 
#include <thread>
#include <unordered_set>
#include <vector>
#include <memory.h>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <stdio.h>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <random>
#include <string>
#include <cassert>


#define getcx _getchar_nolock

using namespace std;
 
namespace std
{
	string to_string(string const& s) { return '"' + s + '"'; }
	string to_string(char c) { return string(1, c); }
	string to_string(const char* s) { return to_string((string)s); }
	string to_string(bool b) { return (b ? "true" : "false"); }
 
	template <class T1, class T2>
	string to_string(pair<T1, T2> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
 
	template <class T>
	string to_string(T c)
	{
		string s = "[";
		for (auto vvv : c) { s += to_string(vvv) + ","; }
		s += "]";
		return s;
	}
 
	void debug_impl() { cerr << endl; };
 
	template <typename T1, typename... T2>
	void debug_impl(T1 a, T2 ... b)
	{
		cerr << " " << to_string(a);
		debug_impl(b...);
	}
}
 
template <typename T>
struct reversion_wrapper
{
	T& iterable;
};
 
template <typename T>
auto begin(reversion_wrapper<T> w) { return std::rbegin(w.iterable); }
 
template <typename T>
auto end(reversion_wrapper<T> w) { return std::rend(w.iterable); }
 
template <typename T>
reversion_wrapper<T> reverse(T&& iterable) { return { iterable }; }
 
 
#ifdef __ASD__
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_impl(__VA_ARGS__)
//#define endl "\n"
#else
#define dbg(...) ;
//#define endl "\n"
#endif
 
#define lng long long

int main()
{
#ifdef __ASD__
	auto start_t = chrono::steady_clock::now();
	freopen("input.txt", "r", stdin);
	//freopen("nul", "w", stderr);
	//freopen("output.txt", "w",  stdout);
#else
	ios_base::sync_with_stdio(false);
#endif
	int n;
	cin >> n;
	int k;
	cin >> k;
	int q;
	cin >> q;
	vector<int> a(n, k-q);
	while(q--)
	{
		int x;
		cin >> x;
		--x;
		a[x]++;
	}

	for(int i=0;i<n;i++)
	{
		if (a[i]>0)cout<<"Yes"; else cout<<"No";
		cout<<endl;
	}
	

	
	
#ifdef __ASD__
	auto finish_t = chrono::steady_clock::now();
	cerr << "Elapsed " << chrono::duration_cast<chrono::milliseconds>(finish_t - start_t).count() << " ms" << endl;
#endif
	return 0;
}


Measured memory_bytes: 1024
import math


class BinaryIndexedTree():
    def __init__(self, N):
        self.N = N
        self.arr = [0] * (N+1)

    def query(self, i):
        ret = 0
        i += 1
        while i:
            ret += self.arr[i]
            lsb = i & (-i)
            i -= lsb
        return ret

    def add(self, i, v):
        i += 1
        while i < self.N+1:
            lsb = i & (-i)
            self.arr[i] += v
            i += lsb

    def search(self, x):
        pos = 0
        cur = 0
        idx = 2 ** int(math.log(self.N, 2))
        while idx >= 1:
            if pos + idx <= self.N and cur + self.arr[pos+idx] < x:
                cur += self.arr[pos+idx]
                pos += idx
            idx //= 2
        return pos


def main():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))
    bit = BinaryIndexedTree(N)
    for i, a in enumerate(A):
        bit.add(i, a)
    for _ in range(Q):
        qtype, a, b = map(int, input().split())
        if qtype == 0:
            bit.add(a, b)
        else:
            ans = bit.query(b-1) - bit.query(a-1)
            print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 132908
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<ll, ll>;
const int INF = 0x3f3f3f3f;
int main() {
  char x;
  cin >> x;
  if (isupper(x)) {
    cout << "A" << endl;
  } else {
    cout << 'a' << endl;
  }
}

Measured memory_bytes: 3600
export class Main {
  static main(input: string): string {
    const tmp: string[] = input.split("\n");
    const [a, v]: number[] = tmp.shift().split(" ").map(int => parseInt(int));
    const [b, w]: number[] = tmp.shift().split(" ").map(int => parseInt(int));
    const [t]: number[] = tmp.shift().split(" ").map(int => parseInt(int));
    return `${Math.abs(a - b) + w * t <= v * t ? 'YES' : 'NO'}`;
  }
}
console.log(Main.main(require("fs").readFileSync("/dev/stdin", "utf8")));


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

int main(void){
   int x;
   int c = 1;
   while(true) {
       cin >> x;
       if(x == 0) {
           break;
       }
       cout << "Case " << c << ": " << x << endl;
       c = c + 1;
   }
}


Measured memory_bytes: 3076
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>

using namespace std;
const long long INF = (long long)1e18;

int main(){
	int n, m, ans = 0;
	cin >> n >> m;
	vector<tuple<int, int, long long>> e(m);
	for(int i = 0; i < m; i++){
		int a, b;
		long long c;
		cin >> a >> b >> c;
		e[i] = tie(a, b, c);
	}
	vector<long long> d(n + 1, -INF);
	d[1] = 0;
	int cnt = 0;
	bool nupdate;
	while(true){
		bool update = false;
		nupdate = false;
		for(int i = 0; i < m; i++){
			int from, to;
			long long cost;
			tie(from, to, cost) = e[i];
			if(d[from] != -INF && d[from] + cost > d[to]){
				d[to] = d[from] + cost;
				update = true;
				if(to == n) nupdate = true;
			}
		}
		if(!update) break;
		if(cnt == m) break;
		cnt++;
	}
	if(nupdate){
		cout << "inf" << endl;
	}else{
		cout << d[n] << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int gcd(int a,int b){
if(a<b){int w=a;
        a=b;
        b=w;
       }
  if(a%b!=0)return gcd(b,a%b);
  else return b;
}
int main(void){
int k;
  scanf("%d",&k);
  long sum=0;
  for(int i=1;i<=k;i++){
	for(int j=1;j<=k;j++){
		for(int l=1;l<=k;l++){
		int x=gcd(l,j);
          sum+=gcd(x,i);
        }
    }
  }
  printf("%ld",sum);
  return 0;
}

Measured memory_bytes: 1732
import std.algorithm;
import std.bigint;
import std.concurrency;
import std.container;
import std.conv;
import std.functional;
import std.format;
import std.math;
import std.meta;
import std.numeric;
import std.random;
import std.range;
import std.stdio;
import std.string;
import std.traits;
import std.typecons;


auto solve(long N, long[] A) {
    return A.reduce!gcd;
}


void main() {
    auto input = stdin.byLine.map!split.joiner;

    long N;
    N = input.front.to!long;
    input.popFront;

    long[] A = new long[](cast(size_t) (N));
    foreach (i; 0 .. cast(size_t) (N)) {
        A[i] = input.front.to!long;
        input.popFront;
    }

    static if (is(ReturnType!solve == void))
        solve(N, A);
    else
        solve(N, A).writeln;
}


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

int main(){
  int N,M;
  cin >> N >> M;
  vector<vector<int> >v(N+1);
  for(int i=0;i<M;i++){
    int A,B;
    cin >> A >> B;
    v.at(A).push_back(B);
    v.at(B).push_back(A);
  }
  vector<int> ans(N+1,-1);
  queue<int> que;
  // vector<bool> flag(N+1,false);
  // vector<int> pre(N+1,-1);
  // flag.at(1)=true;
  que.push(1);
  while(!que.empty()){
    int x=que.front();
    que.pop();
    for(auto y:v.at(x)){
      if(ans.at(y)==-1){
        // flag.at(y)=true;
        que.push(y);
        // pre.at(y)=x;
        ans.at(y)=x;
      }
    }
  }
  // if(pre.at(1)==-1){
  //   cout << "No" << endl;
  //   return 0;
  // }
  for(int i=2;i<=N;i++){
    if(ans.at(i)==-1){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  for(int i=2;i<=N;i++){
    cout << ans.at(i) << endl;
  }
  return 0;
}


Measured memory_bytes: 10104
//#include <bits/stdc++.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
#define int long long
#define ll long long
#define ld long double
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define req(i,n) for(long long i=n-1; i>=0; i--)
#define range(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define onBoard(y,x) (y>=0 && y<h && x>=0 && x<w)
#define vint vector<int>
#define pri_que priority_queue
#define vvint vector<vector<int>>
#define vstr vector<string>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a/gcd(a,b)*b;}
const long long dx[8]={1,0,-1,0,1,-1,-1,1};
const long long dy[8]={0,1,0,-1,1,1,-1,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    int h,w; cin >> h >> w;
    int n; cin >> n;
    vint a(n); rep(i,n) cin >> a[i];
    vvint g(h,vint(w,0));

    int y=0,x=0;
    rep(i,n){
        rep(j,a[i]){
            g[y][x]=i+1;
            //cout<<i+1<<' ';
            if(y%2==0){
                if(x==w-1){
                    y++;
                    continue;
                }
                x++;
            }else{
                if(x==0){
                    y++;
                    continue;
                }
                x--;
            }
        }
    }
    rep(i,h){
        rep(j,w){
            if(j) cout<<' ';
            cout<<g[i][j];
        }
        cout<<endl;
    }
}   

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

using namespace std;

int v[55];
int main() {
    
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i)
        cin >> v[i];

    int ans = 0;

    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            ans += (v[i] * v[j]);
    cout << ans << "\n";

    return 0;
}


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

#define pb push_back
#define mp make_pair
#define all(n) (n).begin(),(n).end()
#define fi first
#define se second

typedef pair<int, int> PII;
typedef long long ll;

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

	int n;
	cin >> n;
	int a[100005][3];
	memset(a,0,sizeof(a));
	for (int i = 1; i <= n; i++) cin >> a[i][0] >> a[i][1] >> a[i][2];

	int dp[100005][3];
	memset(dp,0,sizeof(dp));
	dp[1][0]=a[1][0];
	dp[1][1]=a[1][1];
	dp[1][2]=a[1][2];
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (j==k) continue;
				dp[i+1][k]=max(dp[i+1][k],dp[i][j]+a[i+1][k]);
			}
		}
	}
	cout << max({dp[n][0], dp[n][1], dp[n][2]}) << "\n";

}

Measured memory_bytes: 5968
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <numeric>
#include <functional>
#include <sstream>
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cctype>
#include <cstdio>
#include <cassert>
using namespace std;

#define EPS 1e-12
#define ull unsigned long long
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll> 
#define VVI vector<vector<ll> >
#define VVVI vector<vector<vector<ll>>>
#define VVVVI vector<vector<vector<vector<ll>>>>
#define REP(i,n) for(ll i=0,_n=(n);(i)<(ll)_n;++i)
#define REPR(i,n) for(ll i=(ll)(n)-1;0<=(i);--i)
#define RANGE(i,a,b) for(ll i=(ll)a,_b=(ll)(b);(i)<_b;++i)
#define RANGER(i,a,b) for(ll i=(ll)(b)-1,_a=(ll)(a);(_a)<=i;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define ALLR(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define POPCOUNT __builtin_popcount
#define POPCOUNTLL __builtin_popcountll
#define CLEAR(table, v) memset(table, v, sizeof(table));
#define UNIFORM_DOUBLE(a, b) (((b-a)*(double)rand()/RAND_MAX)+a) // [a, b) 
#define UNIFORM_LL(a, b) (ll)UNIFORM_DOUBLE(a, b) // [a, b) 
#define IN(v, lo, hi) ((lo)<=(v) && (v)<(hi))
#define DD(v) cout<<#v<<": "<<v<<endl
#define FI first
#define SE second
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const map<T0, T1>& v) { for( typename map<T0, T1>::const_iterator p = v.begin(); p!=v.end(); p++ ){os << p->first << ": " << p->second << " ";} return os; }
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const pair<T0, T1>& v) { os << v.first << ": " << v.second << " "; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << " "; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const set<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const deque<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<vector<T> >& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << endl; } return os; }
template<typename T>void maxUpdate(T& a, T b) {a = max(a, b);}
template<typename T>void minUpdate(T& a, T b) {a = min(a, b);}
string YN(bool v) { return v ? "Yes":"No"; }

#define INF (1LL<<60)

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N;
	string s, t;
	while(cin>>N>>s>>t) {
		ll ans=INF;
		RANGE(l, N, N*2+1) {
			ll ok=1;
			string v(l, ' ');
			REP(i, N) v[i]=s[i];
			REP(i, N) if(v[l-N+i]!=' '&&v[l-N+i]!=t[i]) ok=0;
			if(ok) minUpdate(ans, l);
		}
		
		cout<<ans<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int N;
    cin >> N;
    vector<string> s(N);
    vector<int> t(N);
    rep(i, N) { cin >> s[i] >> t[i]; }
    string X;
    cin >> X;
    int check = 0;
    rep(i, N) {
        if(s[i] == X) {
            check = i;
            break;
        }
    }
    int res = 0;
    for(int i = check + 1; i < N; i++) {
        res += t[i];
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 764
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int N; cin >> N;
	vector<int> T(N);
	for (int i = 0; i < N; i++) cin >> T[i];
	int sum = accumulate(T.begin(), T.end(), 0);
	int M; cin >> M;
	for (int i = 0; i < M; i++) {
		int p, x; cin >> p >> x;
		cout << sum - T[p - 1] + x << endl;
	}
}

Measured memory_bytes: 256
from collections import deque

N = int(input())
adj = {u: [] for u in range(1, N+1)}
for i in range(1, N):
    u, v, w = map(int, input().split())
    adj[u].append((v, w))
    adj[v].append((u, w))

color = {}
queue = deque()
queue.append((0, 1, 0))  # (parent-color, child, distance)

while len(queue) > 0:
    pc, c, d = queue.popleft()
    if c in color:
        continue
    color[c] = pc if d % 2 == 0 else 1 - pc
    for v, w in adj[c]:
        queue.append((color[c], v, w))

for u in range(1, N+1):
    print(color[u])


Measured memory_bytes: 58340
#include <bits/stdc++.h>
#define endl "\n"
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;
const int INF = 0x3f3f3f3f;
const double pi = acos(-1);
using namespace std;

int main() {
    IOS
	string s;
	cin >> s;
  	int cnt = 0;
  	for (int i = 0; i < (int) s.size(); ++i) {
    	cnt += s[i]=='x';
    }
  	cout << (cnt > 7 ? "NO": "YES") << endl;
    return 0;
}



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

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef long double LD;
typedef pair<LD, LD> PLDLD;

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

LL MOD=1000000007;

int main()
{
    int n;
    cin>>n;
    vector<int> a(n);
    REP(i,n)   
        cin>>a[i];
    LL sum=1;
    int muri=0;
    REP(i,n)
    {
        if(i==0)continue;
        
        if(i==1)
        {
            sum*=2;
            if(a[i]<3)muri++;
            continue;
        }

        sum*=i+1-muri;
        sum%=MOD;
        muri=max(muri, ((i+1)*2-1 - a[i] +1)/2);
    }

    cout<<sum<<endl;
}


Measured memory_bytes: 640
import java.util.*;
class Restaurant {
    String city;
    int point;
    int i;
    public Restaurant(String city, int point, int i) {
        this.city = city;
        this.point = point;
        this.i = i;
    }
}
class RestaurantComparator implements Comparator<Restaurant>{
    @Override
    public int compare(Restaurant restaurant1, Restaurant restaurant2){
      int ans=restaurant1.city.compareTo(restaurant2.city);
          if(ans!=0){
            return ans;
          }
            return Integer.compare(restaurant1.point, restaurant2.point)*-1;
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Restaurant> list = new ArrayList<Restaurant>();
        int n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            String city = sc.next();
            int point = sc.nextInt();
            list.add(new Restaurant(city, point, i));
        }
        Collections.sort(list, new RestaurantComparator());
        for (Restaurant restaulant: list) {
            System.out.println(restaulant.i);
        }
    }
}

Measured memory_bytes: 35792
#!/usr/bin/env python3

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    Amax=A[-1]+1
    dp = [True]*Amax
    ans=0
    a_temp=set()
    a_tempcheck=set()
    for a in A:
        if dp[a]:
            ans+=1
            a_temp.add(a)
            for i in range(a, Amax, a):
                dp[i] = False
        else:
            if a not in a_tempcheck:
                if a in a_temp:
                    ans-=1
                    a_tempcheck.add(a)
    print(ans)
    
if __name__ == "__main__":
    main()


Measured memory_bytes: 39336