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

#define rep(i, a) for (int i = 0; i < (a); ++i)
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define FORV(a, A) for (auto &a : A)

using namespace std;
using ll = long long;
using P = pair<int, int>;

map<P, int> I;
int k = 0;
vector<vector<int>> G;

int dfs(int a, int b, int prev_col) {
  int col = 0;
  for (int v : G[a]) {
    if (v == b) continue;
    if (col == prev_col) col++;
    if (v < a)
      I[P(v, a)] = col;
    else
      I[P(a, v)] = col;
    dfs(v, a, col);
    col++;
  }
  return 0;
}

void Main() {
  int n;
  cin >> n;
  G.resize(n);
  vector<P> vp;
  rep(i, n - 1) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
    vp.emplace_back(a, b);
  }
  int k = 0;
  rep(i, n) k = max(k, (int)G[i].size());
  dfs(0, 0, -1);
  cout << k << endl;
  rep(i, n - 1) cout << I[P(vp[i].first, vp[i].second)] + 1 << endl;
  return;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}


Measured memory_bytes: 14972
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <limits.h>
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

std::vector<int> v[200001];
int sz[200001];

void dfs(int index, int& cnt, std::vector<int>& mark)
{
    //cout << "--- index:" << index << ", cnt:" << cnt << endl;
    //int sz = v[index].size();
    for(int i=0; i<sz[index]; i++){
        if(mark[v[index][i]] == 0){
            mark[v[index][i]] = 1;
            cnt++;
            //cout << "    next:" << v[index][i] << endl;
            dfs(v[index][i], cnt, mark);
        }
            
    }
}
 
int main()
{
    int n, m;
    cin >> n >> m;
 
    //std::vector<int> a, b;
    
    for(int i=0; i<m; i++){
        int tmp1, tmp2;
        cin >> tmp1 >> tmp2;
        //a.push_back(tmp1);
        //b.push_back(tmp2);
        v[tmp1].push_back(tmp2);
        v[tmp2].push_back(tmp1);
    }
    
    for(int i=0; i<=n; i++){
        std::sort(v[i].begin(), v[i].end());
        v[i].erase(std::unique(v[i].begin(), v[i].end()), v[i].end());
        sz[i] = v[i].size();
        //cout << v[i].size() << endl;
    }
    
    int maxcnt = 0;
    std::vector<int> mark(n+1);
    for(int i=0; i<n; i++){
        
        int cnt = 1;
        mark[i+1] = 1;
        //cout << "***" << endl;
        dfs(i+1, cnt, mark);
        if(maxcnt < cnt) maxcnt = cnt;
    }
 
    cout << maxcnt << endl;
    
 
    return 0;
}

Measured memory_bytes: 28124
#include<cstdio>
#define ll long long int
using namespace std;
const int mod = 1000000007;

ll qpow(ll x, ll y)
{
    ll res=1;
    while(y)
    {
        if(y&1) res=res*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return res;
}

int main()
{
    ll m, n;
    scanf("%lld%lld", &m, &n);
    printf("%lld\n", qpow(m, n));
    return 0;
}

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

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

int main(){
  LL n,m;
  cin >> n >> m;
  if(2*n>=m){
    cout << m/2 << endl;
  }else{
    cout << n+(m-2*n)/4 << endl;
  }
  return 0;
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { each(x, v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n;
  cin >> n;
  vector<vi32> f(n, vi32(10));
  cin >> f;
  vector<vi32> p(n, vi32(11));
  cin >> p;
  i64 ans = -1e18;
  reps(i, bit32(10) - 1) {
    i64 sum = 0;
    vi32 cnt(n);
    rep(j, 10) rep(k, n) {
      if (!(bit32(j) & i)) continue;
      if (!f[k][j]) continue;
      cnt[k] += 1;
    }
    rep(j, n) {
      sum += p[j][cnt[j]];
    }
    amax(ans, sum);
  }
  cout << ans << endl;
}

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

int main()
{
    int n, k, x, y;
    cin >> n >> k >> x >> y;
    int ans = 0;
    int m = 0;
    m = min(n, k);
    ans = m * x + (n - m) * y;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
x,y,a,b,c=map(int,input().split())
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
p.sort()
q.sort()
pp=p[-x:]
qq=q[-y:]

eat=[]
eat.extend(pp)
eat.extend(qq)
eat.extend(r)
eat.sort()
e=eat[(-x-y):]
print(sum(e))

Measured memory_bytes: 22720
import java.util.Scanner;

public class Main {

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

		if ( n % 2 == 1 ) {
			System.out.println("No");
			in.close();
			return;
		}

		String s = in.next();
		String half1 = s.substring(0, n / 2);
		String half2 = s.substring(n / 2);
		
		System.out.println( half1.equals(half2) ? "Yes" : "No");

		in.close();
	}
}

Measured memory_bytes: 23636
import java.util.*;

class Main{
    static int[][] field;
    static int w,h;
    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);

	int n = sc.nextInt();

	while(n!=0){

	    w = sc.nextInt();
	    h = sc.nextInt();

	    field = new int[n][2];
	    for(int i=0; i<n; i++){
		field[i][0] = sc.nextInt();
		field[i][1] = sc.nextInt();
	    }

	    int s = sc.nextInt();
	    int t = sc.nextInt();

	    int count = 0;
	    int max = 0;
	    for(int i=1; i<=h; i++){
		for(int j=1; j<=w; j++){
		    count = 0;
		    for(int k=0; k<n; k++){
			if(field[k][0]>=j && field[k][0]<=j+s-1 && field[k][1]>=i && field[k][1]<=i+t-1)count++;
			//count = getCount(i,j,s,t);
			//System.out.println("count"+count);
			//if(count>max)max = count;
		    }
		    if(count>max)max = count;
		}
	    }	   
	    
	    System.out.println(max);

	    n = sc.nextInt();
	}
    }

    public static int getCount(int x, int y, int s, int t){
	if(x+s>w+1 || y+t>h+1)return 0;
	int count = 0;
	for(int i=y; i<y+t; i++){
	    for(int j=x; j<x+s; j++){
		//System.out.println("x:"+j+" y:"+i);
		if(field[i][j]==1)count++;
	    }
	}
	return count;
    }
}

Measured memory_bytes: 12000
import java.util.Scanner;

public class Main {

    private void execute() throws Exception {
        Scanner sc = new Scanner(System.in);
        String[] md1 = sc.nextLine().split(" ");
        String[] md2 = sc.nextLine().split(" ");
        int m1 = Integer.parseInt(md1[0]);
        int m2 = Integer.parseInt(md2[0]);
        if (m1 == m2) {
            System.out.println("0");
        } else {
            System.out.println("1");
        }
    }

    public static void main(String[] args) {
        try {
            new Main().execute();
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }

}

Measured memory_bytes: 23636
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int x = sc.nextInt();
    int[] a = new int[n];
    for(int i=0;i<n;i++) a[i] = sc.nextInt();
    Arrays.sort(a);
    int cnt=0;
    for(int i=0;i<n;i++){
      if(x-a[i]>=0){
        x-=a[i];
        cnt++;
      }else x=0;
    }
    if(x>0&&cnt>0) cnt--;
    System.out.println(cnt);
  }
}

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

#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;

using namespace std;





void one_case() {
    int n, k;
    cin >> n >> k;
    map<int, int> mp;
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        ++mp[a];
    }
    vector<pair<int, int>> a;
    for (auto p : mp) {
        a.pb(p);
    }
    sort(a.begin(), a.end(), [] (auto& l, auto& r) {
        return l.second < r.second;
    });
    int op = 0;
    for (int i = 0; i + k < a.size(); ++i) {
        op += a[i].second;
    }
    cout << op << "\n";
}


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


    int t = 1;
//    cin >> t;
    while (t--) {
        one_case();
    }

    return 0;
}


Measured memory_bytes: 11768
using System;
using System.Linq;

class Program {
    static void Main(string[] args) {
        int x = Cin.Ni();
        int y = Cin.Ni();
        int z = Cin.Ni();
        int ans = (x - z) / (y + z);

        Console.WriteLine(ans);

    }
}
public struct Parts {
    public int Size;
    public int Count;

    public Parts(int size, int count) {
        Size = size;
        Count = count;
    }
}

public class Cin {
    private static string[] s = new string[0];
    private static int i = 0;

    private static char[] cs = new char[] { ' ' };

    public static string Next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return Next();
    }

    public static int Ni() {
        return int.Parse(Next());
    }

    public static long NextLong() {
        return long.Parse(Next());
    }

    public static double NextDouble() {
        return double.Parse(Next());
    }

}


Measured memory_bytes: 13140
#pragma GCC optimize ("-O3","unroll-loops")
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>


#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<'\n';
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
//#define int unsigned long long
#define all(x) (x).begin(), (x).end()
#define double long double

using namespace std;

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

int MOD = 998244353;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;
typedef pair<int, int>P;
const int MAX = 200020;


set<int>st;
int A[100010], B[100010], N;
void add_div(int x) {
	st.insert(x);
	for (int i = 2; i*i <= (x); i++) {
		if (x%i == 0) {
			st.insert(i);
			st.insert(x / i);
		}
	}
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	string S, T; cin >> S >> T;
	int N = S.size();
	S += S;
	
	REP(i, N) {
		//print(S.substr(i, N));
		if (S.substr(i, N) == T) {
			print("Yes");
			return 0;
		}
	}
	print("No");
}


Measured memory_bytes: 256
'use strict'

const main = (INPUT) => {
  const tmp = INPUT.split('\n').map(n => Number(n))
  tmp.shift()
  let input = tmp.sort((a, b) => b - a)
  let ans = 0;
  for (let i = 0; i < input.length; i++) {
    if (i == 0) {
      ans += input[i] / 2
    } else {
      ans += input[i]
    }
  }
  console.log(ans);
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'))


Measured memory_bytes: 21064
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); i++)
#define rep(i, n) rep2(i, 0, n)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
const int INF = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS = 1e-10;
const int MOD = int(1e9)+7;
template<typename T> inline bool chmin(T& a, T b) {if(a>b) {a=b; return true;} return false;}
template<typename T> inline bool chmax(T& a, T b) {if(a<b) {a=b; return true;} return false;}

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

int main() {
  int H, W; cin >> H >> W;

  vector<string> field(H);
  for (int h = 0; h < H; ++h) cin >> field[h];

  vector<vector<int>> dist(H, vector<int>(W, INF));
  queue<P> que;
  rep(h, H) rep(w, W) {
    if (field[h][w] == '#') {
      dist[h][w] = 0;
    }
    que.push(P(h, w));
  }

  while (!que.empty()) {
    auto u = que.front(); que.pop();
    for (int dir = 0; dir < 4; ++dir) {
      int vh = u.first + dx[dir];
      int vw = u.second + dy[dir];
      if (vh < 0 || vh >= H || vw < 0 || vw >= W) continue;
      if (chmin(dist[vh][vw], dist[u.first][u.second] + 1)) {
        que.push(P(vh, vw));
      }
    }
  }

  int ans = 0;
  rep(h, H) rep(w, W) chmax(ans, dist[h][w]);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 16272
# debug
debugFlag = ( ARGV[0] != nil )
p "==== DEBUG MODE ====" if debugFlag

# input
inputs = []
lc = 0
while l = $stdin.gets do
  if false
    inputs << l.chomp.split(" ").map(&:to_s)
  else
    inputs << l.chomp.split(" ").map(&:to_i)
  end
  lc += 1
end

# input check
if debugFlag
  p "--- INPUT (begin) ---"
  inputs.each do |l_i|
    p l_i
  end
  p "--- INPUT (end) ---"
  print "\n"
end

n = inputs[0][0]
m = inputs[0][1]

checkarr = inputs[1..-1]

mat = []
checkarr.each do |cd_i|
  c_i = cd_i[1..-1]
  vec_i = [0]*m
  c_i.each do |c_ij|
    vec_i[c_ij-1] = 1
  end
  mat << vec_i
end

if debugFlag
  p "n = #{n}"
  p "m = #{m}"
  mat.each do |m_i|
    p m_i
  end
end

resCnt = 0
m.times do |i|
  failFlag = false
  n.times do |j|
    if mat[j][i] == 0
      failFlag = true
      break
    end
  end
  resCnt += 1 if failFlag == false
end
puts resCnt

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

int n,m;
vector<int> k;
vector<vector<int>> s;
vector<int> p;
bool allon(int bit){
  rep(i,m){
    int count = 0;
    rep(j,k[i]){
      if(bit & (1<<s[i][j])) count++;
    }
    if(count%2 != p[i]) return false;
  }
  return true;
}

int main(){
  cin>>n>>m;
  k.resize(m);
  s.resize(m);
  rep(i,m){
    cin>>k[i];
    s[i].resize(k[i]);
    rep(j,k[i]){
      cin>>s[i][j];
      s[i][j]--;
    }
  }
  p.resize(m);
  rep(i,m) cin>>p[i];
  
  int ans = 0;
  rep(bit,1<<n){
    if(allon(bit)) ans++;
  }
  cout << ans << endl;
}

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

int main(){
  int h,w,k;
  cin >> h >> w >> k;
  vector<string> s(h);
  int i,j;
  for(i=0;i<h;i++){
    cin >> s.at(i);
  }
  
  vector<int> a(h);
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      if(s.at(i).at(j)=='#'){
        a.at(i)++;
      }
    }
  }
  
  vector<vector<int>> c(h,vector<int> (w));
  i=0;
  while(a.at(i)==0){
    i++;
  }
  int n=i,x=0,m;
  for(i=n;i<h;i++){
    if(a.at(i)==0){
      for(j=0;j<w;j++){
        c.at(i).at(j)=c.at(i-1).at(j);
      }
    }else{
      j=0;
      while(s.at(i).at(j)=='.'){
        j++;
      }
      m=j;
      for(j=m;j<w;j++){
        if(s.at(i).at(j)=='#'){
          x++;
          c.at(i).at(j)=x;
        }else{
          c.at(i).at(j)=x;
        }
      }
      for(j=0;j<m;j++){
        c.at(i).at(j)=c.at(i).at(m);
      }
    }
  }
  for(i=0;i<n;i++){
    for(j=0;j<w;j++){
      c.at(i).at(j)=c.at(n).at(j);
    }
  }
  
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      cout << c.at(i).at(j) << ' ';
    }
    cout << endl;
  }
}

Measured memory_bytes: 1280
/*  
    |\_/|
    |* *|
    \_+_/
*/
#include<bits/stdc++.h>

#define endl '\n'

using namespace std;

int main(){

  cin.tie(0);     // cout と cin の同期を切る
  ios::sync_with_stdio(false);  /* cの stdioストリーム (printfとか)と*/


  stack <int > st;

  stack<int>st2;
  
  string str;

  cin>>str;

  for(int i=0;i<str.length();i++){

    if(str[i]=='B'){
      if(st.size()){
	st.pop();
      }
    }
    else{
      if(str[i]=='1'){
	st.push(1);
      }else{
	st.push(0);
      }
    }

  }

  while(st.size()){

    st2.push(st.top());

    st.pop();

  }

  while(st2.size()){

    cout<<st2.top();

    st2.pop();

  }
  
  cout<<endl;
  
  return 0;

}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main (void)
{
    int n, y;

    cin >> n;
    cin >> y;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            int k = n - i - j;
            if (k < 0) continue;
            if (i * 10000 + j * 5000 + k * 1000 == y) {
                cout << i << " " << j << " " << k << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1 -1" << endl;

    return 0;
}

Measured memory_bytes: 256
# https://atcoder.jp/contests/abc068/tasks/abc068_b


def two_factor(x):
    cnt = 0
    while x % 2 == 0:
        cnt += 1
        x //= 2
    return cnt


N = int(input())
a = list(map(two_factor, range(1, N + 1)))
max_cnt = max(a)
print(a.index(max_cnt) + 1)


Measured memory_bytes: 2940
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

int main(){
    char c;
    int cnt;
    int sum;
    stack<int> s1;
    stack<pair<int, int> > s2;
    for(int i=0; cin >> c; i++){
        if(c == '\\'){
            s1.push(i);
        }else if(c == '/' && s1.size() > 0){
            int bspos = s1.top();
            s1.pop();
            sum += i - bspos;
            int a = i - bspos;
            while(s2.size() > 0 && s2.top().first > bspos){
                a += s2.top().second;
                s2.pop();
            }
            s2.push(make_pair(bspos, a));
        }
    }
    vector<int> ans;
    while(s2.size() > 0){
        ans.push_back(s2.top().second);
        s2.pop();
    }
    reverse(ans.begin(), ans.end());
    cout << sum << endl;
    cout << ans.size();
    for(int i=0; i<ans.size(); i++){
        cout << " ";
        cout << ans[i];
    }
    cout << endl;
}


Measured memory_bytes: 3200
N,M = map(int, input().split())
A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

def is_match(i, j):
  # x, y is each pixel in A
  for xb in range(M):
    for yb in range(M):
      xa = xb+i
      ya = yb+j
      #print("xb: {}, yb:{}, xa:{}, ya:{}".format(str(xb), str(yb), str(xa), str(ya)))
      if B[xb][yb] != A[xa][ya]:
        return False
  return True

# i, j is top left index
for i in range(N-M+1):
  for j in range(N-M+1):
    #print("i: {}, j:{}".format(str(i), str(j)))
    if is_match(i, j):
      print("Yes")
      exit()
print("No")


Measured memory_bytes: 3064
import java.util.*;

public class Main {
	public static void main(String[] args) {
		int i;
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s = sc.next();
		int k = sc.nextInt();
		sc.close();
		sc = null;
		StringBuilder s2 = new StringBuilder();
		for(i=0; i<n; i++) {
			if(s.charAt(i) != s.charAt(k-1)) s2.append('*');
			else s2.append(s.charAt(i));
		}
		System.out.println(s2);
	}
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define repk(i,m,n) for(ll i=m;i<n;i++)
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD1=1e9+7;
const int MOD2=998244353;
const int INF=2*1e9;
ll a[1005];
int main()
{
    ll n,m,sum=0;
    cin>>n>>m;
    rep(i,n)
    {
        cin>>a[i];
        sum+=a[i];
    }
    sort(a,a+n);
    if(a[n-m]*4*m<sum) cout<<"No";
    else cout<<"Yes";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007
 
using namespace std;
typedef long long ll;
int N,A;
int x[55];
ll dp[55][55][2567];
ll Ans;

int main(){

cin>>N>>A;

for(int i=0; i<N; i++) scanf("%d",&x[i]);

dp[0][0][0]=1LL;

for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
        for(int k=0; k<2500; k++){
        dp[i+1][j][k]+=dp[i][j][k];
        dp[i+1][j+1][k+x[i]]+=dp[i][j][k];
        }
    }
}

for(int j=1; j<=N; j++){
    for(int k=1; k<=2500; k++){
        if(k%j==0){
            if(k/j==A) Ans+=dp[N][j][k];
        }
    }
}

cout<<Ans<<endl;

return 0;
 
}

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

using ll = long long;

#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define FORR(i,a,b) for(int i=b-1;i>=a;i--)

#define DEBUG(x) cerr<<#x<<": "<<(x)<<endl

int h;
int w = 5;
int mp[12][5];

int main(){
    while(true){
        cin>>h;
        if(h==0)break;
        REP(i,h)REP(j,w)cin>>mp[i][j];
        int ans = 0;
        while(true){
            bool flag = false;
            REP(i,h){
                REP(j,3){
                    int v = mp[i][j];
                    if(v==0)continue;
                    int k = j+1;
                    while(k<w && mp[i][k]==v)k++;
                    if(k-j<3)continue;
                    ans += v * (k-j);
                    FOR(x,j,k)mp[i][x] = 0;
                    flag = true;
                    break;
                }
            }
            if(!flag)break;
            FORR(i,1,h)REP(j,w)if(mp[i][j]==0){
                int y = -1;
                FORR(k,0,i)if(mp[k][j]!=0){
                    y = k; break;
                }
                if(y==-1)continue;
                swap(mp[i][j], mp[y][j]);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}



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

const string NO = "IMPOSSIBLE";

void solve(long long A, long long B){
    long long X,K;
    X = A + B;
    K = (A+B)/2;
    if (A - B == 0)
        cout << 0 << endl;
    else if(X==K*2)
        cout << K << endl;
    else
        cout << "IMPOSSIBLE" << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(A, B);
    return 0;
}


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

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vector<int>> mi;
typedef vector<vector<pair<int, int>>> w_graph;
typedef vector<vector<int>> uw_graph;

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   	#ifdef DEBUG
		freopen("out.txt", "w", stdout);
	#endif

	ll dp[(int)1e5 + 5];
	int w[105];
	int v[105];
	int n, W;
	cin >> n >> W;
	
	for (int i = 0; i < n; i++) cin >> w[i] >> v[i];
	
	for (int i = 0; i < 1e5 + 5; i++) dp[i] = 0;
	
	for (int i = 0; i < n; i++){
		for (int j = W; j >= 0; j--){
			if (j >= w[i])
			dp[j] = max(dp[j], v[i] + dp[j - w[i]]);
		}
	}
	cout << dp[W] << endl;
	

	return 0;
}


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

using namespace std;
#define fordebug int hoge;cin>>hoge;
#define DEKAI 1000000007;
#define INF 200000000
#define int long long
#define lp(i,n) for(int i=0;i<n;i++)
#define lps(i,j,n) for(int i=j;i<n;i++)
pair<int,char> a[100000],b[100000];
pair<int,char> rr[100000],ll[100000];

signed main(){
	int n;
	cin>>n;
	int a[1000],b[1000];
	int mini=INF;
	lp(i,n){
		cin>>a[i];
		b[i]=a[i];
		mini=min(mini,a[i]);
	}
	sort(b,b+n);
	int x[100000];
	lp(i,n){
		x[b[i]]=i;
	}
	int ans=0;
	bool done[1000]={false};
	lp(i,n){
		if(done[i]||a[i]==b[i]) continue;
		int sum=0,mini2=INF;
		int count=0;
		int j=i;
		while(!done[j]){
			mini2=min(mini2,a[j]);
			sum+=a[j];
			done[j]=true;
			j=x[a[j]];
			count++;
		}
		int memo=sum;
		sum=sum-mini2+mini2*(count-1);
		memo=memo+mini2+mini*2+mini*(count-1);
		ans+=min(sum,memo);
	}
	cout<<ans<<endl;
	return 0;
}


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

int main() {
int x,n;
	cin>>x>>n;
	if(n==0)
		{
			cout<<x;
			return 0;
		}
	int arr[n];
	for(int i=0;i<n;i++)
		cin>>arr[i];
	set<int> s;
	for(int i=0;i<n;i++)
		s.insert(arr[i]);
	int size=s.size(),old,val1,val2;
	old=size;
	s.insert(x);
	size=s.size();
	if(old!=size)
		{
			cout<<x;
			return 0;
		}
	val1=x+1;
	val2=x-1;
	while(1){
		old=size;
		s.insert(val2);
		size=s.size();
		if(old==size)
		{
			val2--;
		}
		else
		{
			cout<<val2;
			return 0;
		}
		old=size;
		s.insert(val1);
		size=s.size();
		if(old==size)
		{
			val1++;
		}
				else
		{
			cout<<val1;
			return 0;
		}
	}
	return 0;
    
}

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

int main() {
    int N;
    cin >> N;
    string S;
    cin >> S;
    vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));

    for (int i = N - 1; i >= 0; i--)
        for (int j = N - 1; j >= 0; j--) {
            if (S[i] == S[j]) dp[i][j] = dp[i + 1][j + 1] + 1;
        }

    int ans = 0;
    rep(i, N) rep(j, N) {
        int n = dp[i][j];
        if (j - n >= i) {
            ans = max(ans, n);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 98176
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
fn main() {
    input! {
          n: [usize;3],
    };

    let mut n: Vec<usize> = n.clone();
    n.sort();
    let s1 = format!("{}{}", n[2].to_string(), n[1].to_string());
    let n1: usize = s1.parse().unwrap();
    println!("{}", n1 + n[0]);
}



Measured memory_bytes: 4352
def p_e():
    from itertools import product
    h, w = map(int, input().split())
    t1 = [list(map(int, input().split())) for _ in range(h)]
    t2 = [list(map(int, input().split())) for _ in range(h)]

    # pythonでbitsetを用いる->boolのDPで2進数の1をTrue, 0をFalseとして扱う
    # 右にxシフト = その値にx足した値    (10001)<<4 -> (100010000)
    m = 160 * 80
    dp = [[0] * w for _ in range(h)]
    dp[0][0] = 1 << m
    for i, j in product(range(h), range(w)):
        v = abs(t1[i][j] - t2[i][j])
        if i > 0:
            dp[i][j] |= dp[i - 1][j]
        if j > 0:
            dp[i][j] |= dp[i][j - 1]
        dp[i][j] = (dp[i][j] << v) | (dp[i][j] >> v)

    ans = m
    for i in range(m * 2):
        if dp[h - 1][w - 1] & (1 << i) > 0:
            ans = min(ans, abs(m - i))
    print(ans)
    
p_e()

Measured memory_bytes: 57820
import sys
sys.setrecursionlimit(100000000)
n = int(input())

tree = [[] for _ in range(n)]
edges = []
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append((b, i))
    tree[b].append((a, i))

ans = [None for _ in range(n-1)]
used = [False for _ in range(n)]
k = 0


def dfs(node, col=-1, parent=-1):
    global k
    if k < len(tree[node]):
        k = len(tree[node])

    c = 1
    for neighbor, i in tree[node]:
        if neighbor == parent:
            continue
        if c == col:
            c += 1
        ans[i] = c
        c += 1
        dfs(neighbor, ans[i], node)


dfs(0)

print(k)
for a in ans:
    print(a)


Measured memory_bytes: 86256
#include<bits/stdc++.h>
#define ll long long
#define ull long long
#define mod 1000000007
using namespace std;
ll binpow(ll x,ll y)/* (x^y)%p in O(log y) */{ll res=1;while (y > 0){if(y&1)res=(res*x);y = y>>1;x=(x*x);}return res;}
ll binpowmod(ll x,ll y,ll p)/* (x^y)%p in O(log y) */{ll res=1;x=x%p;while (y > 0){if(y&1)res=(res*x)%p;y = y>>1;x=(x*x)%p;}return res;}
ll mod_inverse(ll n,ll p)/* Returns n^(-1) mod p */{return binpowmod(n,p-2,p);}
ll gcd(ll x,ll y)
{
	if(y==0)
		return x;
	return gcd(y,x%y);
}
bool comp(int x,int y)
{
	return x>y;
}
bool isPowerOfTwo (ll x)  
{  
    /* First x in the below expression is for the case when x is 0 */
    return x && (!(x&(x-1)));  
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int n,i,k,j;
	cin>>n>>k;
	vector<int> h(n);
	vector<int> cost(n,INT_MAX);
	for(auto &it : h)
		cin>>it;
	cost[0]=0;
	for(i=2;i<=n;i++)
	{
		for(j=max(i-1-k,0);j<i-1;j++)
			cost[i-1]=min(cost[i-1],cost[j]+abs(h[i-1]-h[j]));
	}
	cout<<cost[n-1];
	
}


Measured memory_bytes: 1024
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <ctime>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

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

typedef long double LD;
typedef long long LL;
typedef pair<LL, LL> pll;
typedef pair<int32_t, int32_t> pii;
typedef vector<int32_t> vi;

template <class T>
string sprint_arr(const vector<T> &arr) {
  stringstream ss;
  for (auto t : arr) {
    ss << std::setw(4) << t.second;
  }
  return ss.str();
}

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

  int32_t n;
  cin >> n;
  vector<vector<pll>> dp(n, vector<pll>(n, pll(0, 0)));

  rep(i, n) {
    int64_t l;
    cin >> l;
    dp[i][i] = pll(l, 0);
  }

  loop(w, 2, n + 1) {
    // rep(i, n) { cerr << sprint_arr(dp[i]) << endl; }
    // cerr << endl;

    rep(s, n - w + 1) {
      int64_t cost = INT64_MAX;
      loop(z, s, s + w - 1) {
        int64_t local_cost = dp[s][z].second + dp[z + 1][s + w - 1].second +
                             dp[s][z].first + dp[z + 1][s + w - 1].first;
        if (cost > local_cost) {
          cost = local_cost;
          dp[s][s + w - 1] = pll(dp[s][z].first + dp[z + 1][s + w - 1].first, cost);
        }
      }
    }
  }

  // rep(i, n) { cerr << sprint_arr(dp[i]) << endl; }

  cout << dp[0][n - 1].second;
}

Measured memory_bytes: 2816
#include<iostream>
#include<string>
using namespace std;
int main() {
	string a, b;
	cin >> a >> b;
	for (int i = 0; i < b.size(); i++)cout << a[i] << b[i];
	if (a.size() > b.size())cout << a[a.size() - 1] << endl;
	else cout << endl;
	return 0;
}

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

int main()
{
	int N;
	static int a[200000];
	scanf("%d", &N);
	int all = 0;
	for (int i = 0; i < N; i++) {
		scanf("%d", &a[i]);
		all ^= a[i];
	}
	for (int i = 0; i < N; i++) {
		printf("%d%c", all ^ a[i], (i == N - 1) ? '\n' : ' ');
	}

	return 0;
}


Measured memory_bytes: 3184
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
int main() {
  int n, ans, k;
  string s, t;
  vector< pair<string, int> > T;
  while (cin >> n, n) {
    for (int i = 0; i < n; ++i) {
      cin >> s >> t;
      T.push_back(make_pair(s, 1));
      T.push_back(make_pair(t, -1));
    }
    ans = 0;
    k = 0;
    sort(T.begin(), T.end());
    for (int i = 0; i < 2*n; ++i) {
      k += T[i].second;
      ans = max(ans, k);
    }
    cout << ans << endl;
    T.erase(T.begin(), T.end());
  }
  return 0;
}

Measured memory_bytes: 4060
#include<bits/stdc++.h>
using namespace std;
int main(){
  string S;
  cin>>S;
  bool flag=true;
  for(int i=0;i<S.size();i++){
    if(i%2==0){
      if(S.at(i)=='L'){
        flag=false;
        cout<<"No"<<endl;
        break;
        }
      }
    else{
      if(S.at(i)=='R'){
        flag=false;
        cout<<"No"<<endl;
        break;
      }
    }
  }
  if(flag) cout<<"Yes"<<endl;
  }

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <iomanip>
using namespace std;
#define all(x) x.begin(), x.end()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
int sub(int a, int b) { return (a -= b) < 0 ? a + mod : a; }
int ctz(int x) { return __builtin_ctz(x); }
int clz(int x) { return __builtin_clz(x); }

const int maxn = 305;
string s[maxn];
int res[maxn][maxn];

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  #ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif

  int n, m, k;
  cin >> n >> m >> k;
  for(int i = 0; i < n; i++){
    cin >> s[i];
  }
  int x = 1;
  for(int i = 0; i < n; i++){
    bool ok = 0;
    bool has = 0;
    for(int j = 0; j < m; j++){
      if(s[i][j] == '#') has = 1;
    }
    if(!has) continue;
    for(int j = 0; j < m; j++){
      if(s[i][j] == '#'){
        if(ok){
          x++;
        }
        else{
          ok = 1;
        }
      }
      res[i][j] = x;
    }
    x++;
  }
  for(int i = n - 2; i >= 0; i--){
    for(int j = 0; j < m; j++){
      if(!res[i][j]){
        res[i][j] = res[i + 1][j];
      }
    }
  }
  for(int i = 1; i < n; i++){
    for(int j = 0; j < m; j++){
      if(!res[i][j]){
        res[i][j] = res[i - 1][j];
      }
    }
  }
  for(int i = n - 2; i >= 0; i--){
    for(int j = 0; j < m; j++){
      if(!res[i][j]){
        res[i][j] = res[i + 1][j];
      }
    }
  }
  for(int i = 1; i < n; i++){
    for(int j = 0; j < m; j++){
      if(!res[i][j]){
        res[i][j] = res[i - 1][j];
      }
    }
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      cout << res[i][j] << " ";
    }
    cout << "\n";
  }
}

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


int main() {
  string SA, SB, SC;
  cin >> SA >> SB >> SC;

char turn = 'a';
int posA = 0, posB = 0, posC = 0;

for (int i=0; i< 310; i++){ 
if (turn == 'a') {
  if (posA >= SA.size()) {
    cout << "A" << endl;
    break;
  }
  turn = SA.at(posA);
  posA ++;
}
else if (turn == 'b') {
  if (posB >= SB.size()) {
    cout << "B" << endl;
    break;
  }
  turn = SB.at(posB);
  posB ++;
}
else if (turn == 'c') {
  if (posC >= SC.size()) {
    cout << "C" << endl;
    break;
  }
  turn = SC.at(posC);
  posC ++;
} 
}  
  
}


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


public class Main {

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        int n = sc.nextInt();
        int digit = String.valueOf(n).length();
        int count = 0;
        for (int i = 1; i < digit; i++) {
            if (i % 2 == 1) {
                int ten = 1;
                for (int j = 1; j < i; j++) {
                    ten *= 10;
                }
                count += 9 * ten;
            }
        }
        if (digit % 2 == 1) {
            int ten = 1;
            for (int i = 1; i < digit; i++) {
                ten *= 10;
            }

            count += ((n / ten - 1) * ten) + n % ten + 1;
        }

        System.out.println(count);
    }


    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        public String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return tokenizer.nextToken("\n");
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }


        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
    }
}

Measured memory_bytes: 22356
#include <bits/stdc++.h>
using namespace std;
# define ll  long long int
# define ld  long double
# define pb push_back
# define pp pop_back
# define ff first
# define ss second
# define mp make_pair
# define ac accumulate
# define mod 1000000007
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int p[5005];
int c[5005];
vector<ll> prefixSums;
bool vis[5005];

void dfs(int src, ll currSum){
	if(vis[src])
		return;
	vis[src] = true;
	currSum += c[src];
	prefixSums.push_back(currSum);
	dfs(p[src], currSum);
}

int  main()
{
    #ifndef ONLINE_JUDGE
       freopen("input.txt", "r", stdin);
       freopen("output.txt", "w", stdout);
    #endif
     IOS
     int n, k;
     cin >> n >> k;
     for(int i = 0; i < n; i++){
     	cin >> p[i];
     	p[i]--;
     }
     for(int i = 0; i < n; i++)
     	cin >> c[i];
     ll ans = -1e18;
     for(int i = 0; i < n; i++){
     	memset(vis, false, sizeof(vis));
     	dfs(i, 0);
     	if(prefixSums.back() > 0 && k > (int)prefixSums.size()){
     		ll cycles = (ll)(k/(int)prefixSums.size());
     		ll left = (ll)(k%(int)prefixSums.size());
     		ll maxi = -1e18;
     		for(int x = 0; x < (int)prefixSums.size(); x++)
     			maxi = max(maxi, prefixSums[x]);
     		ans = max(ans, (cycles - 1LL)*(prefixSums.back()) + maxi);
     		maxi = -1e18;
     		for(int x = 0; x < left; x++)
     			maxi = max(maxi, prefixSums[x]);
     		ans = max(ans, (cycles*prefixSums.back()) + maxi);
     	}
     	else{
     		for(int j = 0; j < min((int)prefixSums.size(), k); j++)
     			ans = max(ans, prefixSums[j]);
     	}
     	prefixSums.clear();
     }
     cout << ans;
     return 0;
}

Measured memory_bytes: 3924
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

// rep(i, 100) { cout << i << endl; } => 0 1 2 ... 99
#define rep(i, n) for(int i = 0, i##_len = (n); i < (int)n; i++)

// std::sort(all(v));
#define all(x) (x).begin(), (x).end()

// long long int
using ll = long long;

// utility to cast return value of size function to int
#define SZ(x) ((int)(x).size())

// VS defines "_DEBUG" macro when debug configuration.
#if _DEBUG
#define dump(x) cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl
#else
#define dump(x)
#define debug(x)
#endif

// update max
template<class T>bool chmax(T & prov, const T & cur)
{
	if (cur > prov)
	{
		prov = cur;
		return true;
	}
	return false;
}

// update min
template<class T>bool chmin(T & prov, const T & cur)
{
	if (cur < prov)
	{
		prov = cur;
		return true;
	}
	return false;
}

int main()
{
	string S;
	cin >> S;
	std::sort(S.begin(), S.end());
	if (S[0] == S[1] && S[2] == S[3] && S[0] != S[2])
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        System.out.println(backtrack(n, "0"));
    }

    private static int backtrack(int n, String digits) {
        if (digits.length() > 10) {
            return 0;
        }
        int val = Integer.parseInt(digits);
        if (val > n) {
            return 0;
        }
        int ans = 0;
        if (digits.contains("3") && digits.contains("5") && digits.contains("7")) {
            ans = 1;
        }

        ans += backtrack(n, digits + "3");
        ans += backtrack(n, digits + "5");
        ans += backtrack(n, digits + "7");
        return ans;
    }
}


Measured memory_bytes: 34644
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const int MAX = 510000;

int main() {
  int N;
  string S;
  cin >> N >> S;
  vector<pair<int, int>> WB(N); // S_iまでにある白と黒のマスの個数
  if (S[0]=='.') {
    WB[0].first = 1;
    WB[0].second = 0;
  }
  else {
    WB[0].first = 0;
    WB[0].second = 1;
  }
  for (int i=1; i<N; i++) {
    if (S[i]=='.') {
      WB[i].first = WB[i-1].first+1;
      WB[i].second = i+1-WB[i].first;
    }
    else {
      WB[i].second = WB[i-1].second+1;
      WB[i].first = i+1-WB[i].second;
    }
  }
  int ans = min(N-WB[N-1].first, N-WB[N-1].second);
  // S_iより左は.，S_iより右は#
  for (int i=0; i<N-1; i++) ans = min(ans, WB[i].second+WB[N-1].first-WB[i].first);
  cout << ans << endl;
}

Measured memory_bytes: 2180
use text_io::*;
use std::collections::HashMap;
use std::process::exit;

fn main() {
    let mut n:usize = read!();
    let mut v: [usize; 3] = [10;3];
    let mut m:usize = read!();
    for i in 0..m {
        let s:usize = read!();
        let c:usize = read!();
        if v[s-1] == c ||v[s-1] == 10{
            v[s-1] = c;
        }
        else {
            println!("-1");
            exit(0);
        }
    }
    if n==3{
        if v[0]==10 {
            v[0]=1;
        }
        if v[0]==0 {
            println!("-1");
            exit(0);
        }
        println!("{}",(v[0]%10)*100+(v[1]%10)*10+v[2]%10);
    }
    if n==2 {
        if v[0]==10 {
            v[0]=1;
        }
        if v[0]==0 {
            println!("-1");
            exit(0);
        }
        println!("{}",v[0]*10+v[1]%10);
    }
    if n==1 {
        if v[0]==10 {
            v[0]=0;
        }
        println!("{}",v[0]);
    }
}

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

int N,Q;
vector <int> a[200001];
pair <int,int> p[200001];
ll cnt[200001]={0};
bool path[200001]={0};

void dfs(int pi, int x){
  path[pi]=1;
  cnt[pi]=x;
  for (int i(0);i<a[pi].size();i++){
    if (path[a[pi][i]]==0) dfs(a[pi][i],x+cnt[a[pi][i]]);
  }
  path[pi]=0;
}

int main(){
  cin>>N>>Q;
  for (int i(0);i<N-1;i++){
    int b,c;
    cin>>b>>c;
    a[b].push_back(c);
    a[c].push_back(b);
  }
  int xi(0);
  for (int i(0);i<Q;i++) {
    cin>>p[i].first>>p[i].second;
    cnt[p[i].first]+=p[i].second;
    if (p[i].first == 1) xi += p[i].second;
  }
  dfs(1,xi);
  for (int i(1);i<=N;i++) cout << cnt[i] << " ";
  return 0;
}


Measured memory_bytes: 25984
import sys, re
import math
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul	# 
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd	# 最大公約数
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# -*- coding: utf-8 -*-

s = input()
t = input()

if len(s) + 1 == len(t) and s == t[:len(t) - 1]:
    print("Yes")
else:
   print("No")

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

int main(){
int s;
int a[]={500,100,50,10,5,1};
int b;
while(scanf("%d",&b),b){
	s=0;
	int c=1000-b;
	for(int d=0;d<6;d++){
		int e=c/a[d];
		s+=e;
		c-=e*a[d];
	}
	printf("%d\n",s);
}
}

Measured memory_bytes: 3072
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define N 1000010
#define M 21
#define mod 1000000007
using namespace std;
int all,n,p[N],g[N][M];
inline int updv(int x,int p)
{
	return p=n-p+1,x|(1<<(p-1));
}
inline int delv(int x,int p)
{
	return p=n-p+1,x&(all^(1<<(p-1)));
}
inline int getv(int x,int p)
{
	return p=n-p+1,(x&(1<<(p-1)))>>(p-1);
}
inline int show(int x)
{
	for(int i=1;i<=n;i++) cout<<getv(x,i);
	cout<<endl;return 0;
}
int x[M],y[M],f[N];
int main()
{
	int m,k;scanf("%d%d%d",&n,&m,&k);
	n--,all=(1<<n)-1;
	for(int i=1;i<=k;i++)
	{
		int a,b,c;scanf("%d%d%d",&a,&b,&c);
		x[a]=updv(x[a],b),(c?y[a]=updv(y[a],b):0);
	}
	for(int i=0;i<=all;i++)
	{
		for(int j=1,k=0;j<=n;j++)
			if(getv(i,j))
			{
				k++;
				if(!getv(i,j-1))
					g[i][k]=updv(delv(i,j),j-1);
			}
		for(int j=n;j>=1;j--)
			if(!getv(i,j))
			{	p[i]=updv(i,j);break;	}
	}
	f[0]=1;
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j<=all;j++)
			if(f[j]&&p[j]) (f[p[j]]+=f[j])%=mod;
		for(int t=1;t<=n;t++)
			for(int j=0;j<=all;j++)
				if(f[j]&&g[j][t]) (f[g[j][t]]+=f[j])%=mod;
		for(int j=0;j<=all;j++)
			if((x[i]&j)^y[i]) f[j]=0;
	}
	int ans=0;
	for(int i=0;i<=all;i++) (ans+=f[i])%=mod;
	return !printf("%d\n",ans);
}

Measured memory_bytes: 51456