akhauriyash/Code-Regression huggingface dataset:
/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2020-03-26 15:33:18
**/

#include <iostream>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
#include <bitset>
#include <cassert>
#include <cctype>
#include <iomanip>
#include <random>
#include <utility>
#include <chrono>

using namespace std;

using int64 = long long;

template<class T> using binary_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) { os << '{'; size_t n = vec.size(); for (size_t i = 0; i < n; ++i) { os << vec[i]; if (i != n - 1) os << ','; } os << '}'; return os; }
template<class T, class U> std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) { return os << '{' << p.first << " " << p.second << '}'; }
template<class T, class U> std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) { os << '{'; for (auto it = mp.begin(); it != mp.end(); ++it) { os << '{' << it->first << ':' << it->second << '}'; if (it != --mp.end()) os << ','; } os << '}'; return os; }
template<class T> std::ostream& operator<<(std::ostream& os, const std::set<T>& st) { os << '{'; for (auto it = st.begin(); it != st.end(); ++it) { os << *it; if (it != --st.end()) os << ','; } os << '}'; return os; }
template<class T> std::istream& operator>>(std::istream& is, std::vector<T>& vec) { size_t n = vec.size(); for (size_t i = 0; i < n; ++i) is >> vec[i]; return is; }

#define all(_) begin(_), end(_)
#define rall(_) rbegin(_), rend(_)

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

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}

using graph = std::vector<std::vector<int>>;

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

  int n, q; cin >> n >> q;
  graph g(n);

  for (int i = 0; i < n - 1; ++i) {
    int a, b; cin >> a >> b; --a; --b;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }

  vector<int> counter(n, 0);

  for (int i = 0; i < q; ++i) {
    int p, x; cin >> p >> x;
    --p;
    counter[p] += x;
  }

  auto dfs = [&](const auto& dfs, int cur, int prev) -> void {
    for (int next : g[cur]) {
      if (next == prev) continue;
      counter[next] += counter[cur];
      dfs(dfs, next, cur);
    }
  };

  dfs(dfs, 0, -1);

  for (int i = 0; i < n; ++i) {
    cout << counter[i] << " ";
  }
  cout << '\n';

  return 0;
}

Measured memory_bytes: 20736
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define sort(a)         sort((a).begin(), (a).end())
#define uniq(a)         SORT(a);(a).erase(unique((a).begin(), (a).end()), (a).end())
#define reverse(a)      reverse((a).begin(), (a).end())
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define Yes()           printf("Yes\n")
#define No()            printf("No\n")
#define YES()           printf("YES\n")
#define NO()            printf("NO\n")
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }

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

const ll MOD = 1000000007; // 10^9 + 7

void solve() {
  int n; cin >> n;
  if (n / 10 == 9 || n % 10 == 9) {
    Yes();
  } else {
    No();
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
int main()
{
	string s,ans;
	cin >> s;
	for(int i=0; s[i] != '\0'; i++){
		if(s[i] == 'B'){
			if(ans.size() > 0) ans.pop_back();
		}else ans.push_back(s[i]);
	}
	for(int i=0; ans[i] != '\0'; i++){
		cout << ans[i];
	}
	cout << endl;
	
	return 0;
}


Measured memory_bytes: 256
N, M, C = input().split()
N = int(N)
M = int(M)
C = int(C)

B = []
b = list(map(int, input().split()))

A = []
for i in range(N):
    A.append(list(map(int, input().split())))

results = [[sum(a*b for a,b in zip(x_row, b))] for x_row in A]

working = 0
for result in results:
    if ((result[0] + C) > 0):
        working += 1

print(working)

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

int main() {
	int n;
	scanf("%d", &n);
	vector<int> s(n - 1), c(n - 1), f(n - 1);
	rep(i, n - 1) {
		scanf("%d%d%d", &c[i], &s[i], &f[i]);
	}
	rep(i, n) {
		int ans = 0;
		for (int j = i; j < n - 1; j ++) {
			if (ans < s[j]) { 
				ans = s[j];
			} else if (ans % f[j] != 0) {
				ans += f[j] - ans % f[j];
			}
			ans += c[j];
		}
		printf("%d\n", ans);
	}
        return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
// using namespace __gnu_pbds;
using namespace std;
 
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
typedef pair <long long,long long> ii;
typedef complex<long double> point;


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	ll n;
	cin >> n;
	string s;
	cin >> s;
	ll l = 0;
	ll r = n;
	ll ans = 0;
	while (l <= r){
		ll mid = (l+r)/2;
		unordered_map <string,vector<ll>> mapp;
		for (int z=0;z<n-mid+1;z++){
			string temp = s.substr(z,mid);
			mapp[temp].push_back(z+mid);
		}
		bool ok = false;
		for (auto it = mapp.begin();it != mapp.end();it++){
			ll k = (it->second).size();
			if (it->second[k-1] >= it->second[0]+mid){	
				ok = true;
				break;	
			}
		}
		if (ok){
			ans = max(ans,mid);
			l = mid+1;
		} else {
			r = mid-1;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 6784
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string S;
    cin>>S;
    int count = 0,ans=0;
    for(int i=0;i<S.size();i++)
    {
        if(S[i]=='A' || S[i]=='C' || S[i] == 'G' || S[i]=='T')
        count++;
        else
        {
            ans = max(ans,count);
            count = 0;
        }
    }
    ans = max(ans,count);
    cout<<ans;
    return 0;
}

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


int main(){

	int a, b;
	
	while( cin >> a >> b){
		double x = 0;
		for(; a+b >= pow(10,x);x += 1){
		}
		cout << x << '\n';

	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const ll INF = 1e9;
ll n, ans;
ll a[305][305];
bool bo[305][305];

int main()
{
    scanf("%lld", &n);
//    for(ll i = 1; i <= n; i++) for(ll j = 1; j <= n; j++) a[i][j] = INF;
    for(ll i = 1; i <= n; i++)
    {
        for(ll j = 1; j <= n; j++)
        {
            scanf("%lld", &a[i][j]);
        }
    }
    for(ll k = 1; k <= n; k++)
    {
        for(ll i = 1; i <= n; i++)
        {
            for(ll j = 1; j <= n; j++)
            {
                if(i == k || j == k || i == j) continue;
                if(a[i][j] > a[i][k] + a[k][j]) {printf("-1"); return 0;}
                if(a[i][j] == a[i][k] + a[k][j])
                {
                    bo[i][j] = true;
                }
            }
        }
    }
    for(ll i = 1; i <= n; i++)
    {
        for(ll j = 1; j <= n; j++)
        {
            ans += (1 - bo[i][j]) * a[i][j];
        }
    }
    printf("%lld", ans / 2);
    return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define lli long long int
#define pb push_back
#define mod2 998244353
#pragma GCC optimize("-O2")
#define mod3 127
#define mod 1000000007
#define MAXN 1000000000
#define v32 vector<int>
#define v64 vector<lli>
#define v1024 vector<vector<int>>
#define v4096 vector<vector<lli>>
#define vt vector
#define f(x, y, z) for (lli x = y; x < z; x++)
#define fd(x, y, z) for (lli x = y; x > z; x--)
#define lb lower_bound
#define ld long double
#define m64 map<lli, lli>
#define m32 map<int, int>
#define m64it map<lli, lli>::iterator
#define m32it map<int, int>::iterator
#define fastio                    \
ios_base::sync_with_stdio(0); \
cin.tie(0);                   \
cout.tie(0)
#define ist insert
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define p_q priority_queue
#define min_p_q priority_queue<int, vt<int>, greater<int>>
using namespace std;
using namespace __gnu_pbds;
lli tmod(lli x, lli y)
{
    return (x % y + y) % y;
}
template <typename T>
void DEBUG_ARR(vt<T> a)
{
    f(i, 0, a.size()) cout << a[i] << " ";
    cout << "\n";
}
lli power(lli x, lli y) 
{
    lli res = 1;  
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x)%mod; 
        y = y>>1; 
        x = (x*x)%mod;
    }
    if(res<0)res+=mod;
    return res; 
}

int main()
{   
    fastio;
    lli h;
    cin>>h;
    lli cnt=0;
    while(((1ll)<<cnt)<=h)cnt++;
    cout<<((1ll)<<(cnt))-1<<"\n";
    return 0;
}


Measured memory_bytes: 256
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define VSUM(V) accumulate(ALL(V), 0)
#define MID(a,b,c) (a) < (b) && (b) < (c)
#define MIDe(a,b,c) (a) <= (b) && (b) <= (c)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define IN4(a,b,c,d) cin >> a >> b >> c >> d
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define Vd vector<double>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b != 0 ? gcd(b, a % b) : a;} //最大公約数
int lcm(int a, int b){return a * b / gcd(a, b);}
string toStrUp(string str){char diff = 'A'-'a';REP(i,str.size()) str[i] += diff;return str;}
string gCh(string str, int key){return str.substr(key,1);}

signed main() {
  RAPID;
  // デフォルト変数定義
  int n=0,m=0,a=0,b=0,c=1,d=0,x=0,y=0,z=0;
  string s="",t="";
  //

  // ここから
  IN4(a,b,c,x);
  REP(i,a+1){
  	REP(j,b+1){
      REP(k,c+1){
      	if(500*i+100*j+50*k==x) n++;
      }
    }
  }
  OUT(n);
}


Measured memory_bytes: 384
import java.util.*;

public class Main {    
    public static void main(String[] args){        
        Scanner sc = new Scanner(System.in);                
        
        int N = sc.nextInt();
        int K = sc.nextInt();
        
        int ans = K;
        
        for(int i = 1;i <= N-1;i++){
           ans *= (K-1);       
        }        
        
        System.out.println(ans);
        
    }            
}
        
        
        

Measured memory_bytes: 21844
using System;

namespace AOJ
{
    class Program
    {
        static void Main(string[] args)
        {

            var room = new int[4,3,10];

            for (var e = 0; e < 4;e++ )
            {
                for(var g=0;g<3;g++)
                {
                    for (var k = 0; k < 10;k++ )
                    {
                        room[e, g, k] = 0;
                    }
                }
            }

            var read = Console.ReadLine();
            int num = int.Parse(read),b,v,f;


                for (int i = 0; i < num; i++)
                {
                    read = Console.ReadLine();
                    var temp_string = read.Split(' ');
                    b = int.Parse(temp_string[0])-1;
                    v = int.Parse(temp_string[1])-1;
                    f = int.Parse(temp_string[2])-1;

                    room[b, v, f] += int.Parse(temp_string[3]);
                }

                for (var e = 0; e < 4; e++)
                {
                    for (var g = 0; g < 3; g++)
                    {
                        for (var k = 0; k < 10; k++)
                        {
                            Console.Write(" "+room[e, g, k]);
                        }
                        Console.WriteLine();
                    }
                    if(e<3)
                    {
                        Console.WriteLine("####################");
                    }
                }
        }
    }
}

Measured memory_bytes: 9208
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define pb push_back
typedef long long ll;
typedef pair<ll,ll> P;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;

string s,n,ans;
int main(){
    cin>>s>>n;
for (int i=0;i<s.size();i++){
    if(s[i]==n[i])ans="Yes";
    else {
     ans="No";
     break;
    }
    
}
cout<<ans;
}


Measured memory_bytes: 3636
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;

public class HelloWorld
{

    static long A;
    static long B;
    static long C;
    static long D;
    static long N;
    static SortedDictionary<long, long> dic;
    static public void Main()
    {
        var T = long.Parse(Console.ReadLine());
        for (int i = 0; i < T; i++)
        {
            var inp =
            Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();
            N = inp[0];
            //used = new long[N + 5];
            A = inp[1];
            B = inp[2];
            C = inp[3];
            D = inp[4];
            dic = new SortedDictionary<long, long>();
            dic.Add(1, D);
            dic.Add(0,(long) Math.Pow(10,13) );
            Console.WriteLine(Check(N));
        }
    }

    static long Check(long n)
    {

        if (dic.ContainsKey(n)) return dic[n];

        var tmp2 = n % 2;
        var tmp3 = n % 3;
        var tmp5 = n % 5;
        long ans = n*D;
        if (ans < 0) ans = long.MaxValue;

        if (n % 5 == 0)
        {
            ans = Math.Min(ans, C + Check(n / 5));
        }
        else
        {
            ans = Math.Min(ans, C + D * (5 - tmp5) + Check((n + 5 - tmp5) / 5));
            ans = Math.Min(ans, C + D * tmp5 + Check((n - tmp5) / 5));
        }

        if (n % 3 == 0)
        {
            ans = Math.Min(ans, B + Check(n / 3));
        }
        else
        {
            ans = Math.Min(ans, B + D * (3 - tmp3) + Check((n + 3 - tmp3) / 3));
            ans = Math.Min(ans, B + D * tmp3 + Check((n - tmp3) / 3));
        }

        if (n % 2 == 0)
        {
            ans = Math.Min(ans, A + Check(n / 2));
        }
        else
        {
            ans = Math.Min(ans, D+A* tmp2 + Check((n + tmp2) / 2));
            ans = Math.Min(ans, D+A + Check((n - tmp2) / 2));
        }

        dic.Add(n, ans);
        return ans;
    }

}


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

using namespace std;

#define REP(i, a, n) for (int i = a, _n = n; i <= _n; ++i)
#define DREP(i, a, n) for (int i = a, _n = n; i >= _n; --i)
#define FOR(i, a, n) for (int i = a, _n = n; i < _n; ++i)
#define EREP(i, a) for (int i = first[a]; i; i = edge[i].nxt)
#define debug(x) cout << #x << " = " << x << endl

int a, b, c, d;
int main () {
	scanf ("%d%d%d", &a, &b, &c);
	printf ("%d\n", min(a * b, c));
	return 0;
}


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

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

    long max_num = 0;
    long next_max_num = 0;
    for(int i = 0; i < N; i++)
    {
        if(A[i] > next_max_num)
        {
            next_max_num = min(A[i], max_num);
            max_num = max(A[i], max_num);
        }
    }
    for(int i = 0; i < N; i++)
    {
        if(A[i] == max_num)
        {
            cout << next_max_num << endl;
        }
        else
        {
            cout << max_num << endl;
        }        
    }
}



Measured memory_bytes: 3200
#include<cstdio>

int n, k, r, s, p;
char t[100001];

int main() {
    scanf("%d %d", &n, &k);
    scanf("%d %d %d", &r, &s, &p);
    scanf("%s", t);
    int ans = 0;
    for (int i = 0; i < k; i++) {
        char c = t[i];
        for (int j = i, cnt = 0; j < n; j += k) {
            if (j + k < n && t[j] == t[j + k]) cnt++;
            else {
                switch (t[j]) {
                    case 'r':
                        ans += p * (cnt / 2 + 1);
                        break;
                    case 's':
                        ans += r * (cnt / 2 + 1);
                        break;
                    case 'p':
                        ans += s * (cnt / 2 + 1);
                        break;
                }
                if (j + k < n) c = t[j + k];
                cnt = 0;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using pdd = pair<double, double>;
using uint = unsigned int;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;
const ld PI = acosl(-1);

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

    ll X, K, D;
    cin >> X >> K >> D;

    X = abs(X);
    ll move = min(K, X / D);
    K -= move;
    X -= move * D;

    cout << (K & 1 ? D - X : X) << endl;

    return 0;
}


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

int main(){
    long long k, a, b;
    cin >> k >> a >> b;
    if(k <= a) cout << 1 << endl;
    else if(a <= b) cout << -1 << endl;
    else{
        k -= a;
        long long ans = (k + a - b - 1) / (a - b) * 2 + 1;
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

sx, sy, tx, ty = map(int, read().split())
x = (tx - sx)
y = (ty - sy)
print('U' * y + 'R' * x + 'D' * y + 'L' * (x + 1) + 'U' * (y + 1) + 'R' * (x + 1) + 'DR' + 'D' * (y + 1) + 'L' * (x + 1) + 'U')


Measured memory_bytes: 3060
def main():
    N = int(input())
    A = list(map(int, input().split()))

    m = min(A)
    M = max(A)

    Result = 100000000

    for i in range(m, M+1):
        Result_tmp = 0
        for a in A:
            Result_tmp += (a - i) * (a - i)
        Result = min(Result_tmp, Result)
    print(Result)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main () {
  string S;
  cin >> S;
  vector<long> x, y;
  long co = 0, flag = 0, sumx = 0, sumy = 0;
  for(int i = 0; i < S.size(); i++){
    if(S.at(i) == 'F')co++;
    else{
      if(flag == 0){
        flag = 1;
        if(co == 0)continue;
        x.push_back(co);
        sumx += co;
      } else {
        flag = 0;
        if(co == 0)continue;
        y.push_back(co);
        sumy += co;
      }
      co = 0;
    }
  }
  if(flag == 0){
     x.push_back(co);
     sumx += co;
  } else {
    y.push_back(co);
     sumy += co;
  }
  long a, b;
  cin >> a >> b;
  if(S.at(0) == 'F'){
    a -= x.at(0);
    sumx -= x.at(0);
    x.at(0) = 0;
  }
  if(abs(a) > sumx || abs(b) > sumy){
    cout << "No" << endl;
    return 0;
  }
  vector<long> dpx(sumx * 2 + 1), dpy(sumy * 2 + 1);
  dpx.at(sumx * 2) = 1;
  dpy.at(sumy * 2) = 1;
  for(int i = 0; i < x.size(); i++){
    for(int j = 0; j < dpx.size(); j++){
      if(dpx.at(j) == 1){
        if(j - x.at(i) * 2 >= 0){
          dpx.at(j - x.at(i) * 2) = 1;
        }
      }
    }
  }
  for(int i = 0; i < y.size(); i++){
    for(int j = 0; j < dpy.size(); j++){
      if(dpy.at(j) == 1){
        if(j - y.at(i) * 2 >= 0){
          dpy.at(j - y.at(i) * 2) = 1;
        }
      }
    }
  }
  if(dpx.at(a + sumx) == 1 && dpy.at(b + sumy) == 1)cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N , A , B , C , D ;
  cin  >>  N  ;
  A = N % 10 ;
  B = (N - A )/10 % 10  ;
  C = (N -10*B - A)/100 % 10  ; 
  D = (N -100*D -10*B -A)/1000  ;
 // cout << A << endl;
 // cout << B << endl;
 // cout << C << endl;
 // cout << D << endl;
  
  if ((B == C)&&(C == D)|| (A == B)&&(B == C )){
    cout << "Yes" <<endl; 
  }
  else{ 
    cout << "No" << endl;
  }
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define ALL(x) (x).begin(), (x).end()
#define REP(i ,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
typedef vector<int>vint;
typedef vector<ll>vll;
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int main()
{
  int N;
  cin >> N;
  vint H(N);
  cin >> H;
  
  string ans = "Yes";
  int cnt = 0;
  for(int i=0; i<H.size()-1; i++){
    if(0 > H[i+1]-H[i])cnt++;
    if(0 < H[i+1]-H[i])cnt = 0;
    if(2 == cnt){
      ans = "No";
      break;
    }
    if(H[i]-H[i+1] > 1){
      ans = "No";
      break;
    }
  }
  
  cout << ans << endl;
}

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

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define double long double
#define pb push_back
#define pii pair <int, int>
#define ff first
#define ss second
#define watch(x) cerr << "\n" << (#x) << " is " << (x) << endl

void __print(int x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "\n[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

const int mod = 1e9 + 7;
//const int mod = 998244353;


signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  string a, b; 
  cin >> a >> b;
  debug(a, b, b+a);
  cout << b+a << '\n';
}


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

#define rep(i,N) for(int i=0;i<N;i++)
#define rep2(i,N) for(int i=1;i<=N;i++)
using namespace std;
long long  INF=1e18;
long long mod=1e9+7;

//status unsolved
bool cmp1(pair<long long,long long>p1,pair<long long,long long>p2){
    return p1.second<p2.second;
}

bool cmp2(pair<long long,long long>p1,pair<long long,long long>p2){
    return p1.first<p2.first;
}
int main(){
    int n;
    cin>>n;

    vector<pair<long long,long long>>range(n);
    rep(i,n){
        long long a,b;
        cin>>a>>b;
        range[i]=make_pair(a,b);
    }
    //右ソート
    sort(range.begin(),range.end(),cmp1);
    long long  right;
    long long right1;
    long long right2;
    if(n%2==1){
        right=range[(n+1)/2-1].second;
    } 
    else{
        right2=range[(n/2)+1-1].second;
        right1=range[(n/2)-1].second;
    }
    //左ソート
    sort(range.begin(),range.end(),cmp2);
    long long left;

    long long  left1=0;
    long long  left2=0;
    if(n%2==1){
        left=range[(n+1)/2-1].first;
    }
    else{
        //left2=(long double)range[(n)/2+1-1].first;
        left1=range[(n/2)-1].first;
        left2=range[(n/2)+1-1].first;
    }
    if(n%2==1){
    cout<<right-left+1<<endl;
    }
    else{
        cout<<right2+right1-(left1+left2)+1<<endl;
    }
    return 0;

}
/*


*/


Measured memory_bytes: 6428
#include <stdio.h>

typedef long long ll;

ll a[100005];

int main(){

	int n;

	scanf("%d",&n);

	int i;

	for(i=0;i<n;i++){
		scanf(" %lld",&a[i]);
	}

	ll sum=0ll;
	ll ans1=0ll;

	for(i=0;i<n;i++){
		sum+=a[i];
		if(i%2==0){
			if(sum<=0ll){
				ans1+=-sum+1ll;
				sum+=-sum+1ll;
			}
		}
		else{
			if(sum>=0ll){
				ans1+=sum+1ll;
				sum+=-sum-1ll;
			}
		}
	}

	sum=0ll;
	ll ans2=0ll;

	for(i=0;i<n;i++){
		sum+=a[i];
		if(i%2==0){
		if(sum>=0ll){
				ans2+=sum+1ll;
				sum+=-sum-1ll;
			}
		}
		else{
			if(sum<=0ll){
			ans2+=-sum+1ll;
			sum+=-sum+1ll;
			}
		}
	}

	if(ans1<ans2){printf("%lld\n",ans1);}
	else{printf("%lld\n",ans2);}

	return 0;
}

Measured memory_bytes: 896
S = input()

word_count = {}
for i in range(len(S)):
    if S[i] in word_count:
        word_count[S[i]] += 1
    else:
        word_count[S[i]] = 1

if len(word_count) == 2 and word_count[S[0]] == 2:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 2940
n, m = map(int, input().split())
l1 = [list(map(int, input().split())) for _ in range(n)]
l2 = [list(map(int, input().split())) for _ in range(m)]

for a, b in l1:
    res_d = float('inf')
    res_n = 0
    for i in range(m):
        c, d = l2[i]
        if res_d > abs(a - c) + abs(b - d):
            res_d = abs(a - c) + abs(b - d)
            res_n = i + 1
    print(res_n)

Measured memory_bytes: 68616
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int maxn = 1e5+7,mod = 1e9+7;
ll read(){
    ll c = getchar(),Nig = 1,x = 0;
    while(!isdigit(c))
        c = getchar();
    if(c == '-')
        Nig = -1,c = getchar();
    while(isdigit(c))
        x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();
    return Nig*x;
}
#define read read()
ll Pow(ll a,int b,ll ans = 1){
    for(;b;b>>=1,a *= a)
        if(b&1)
            ans *= a;
    return ans;
}
int main(){
    ios;
    ll n = read,p = read,ans = 1;
    for(ll i=2;i*i<=p;i++){
        if(p%i)continue;
        int cnt = 0;
        while(p%i==0)
            cnt++,p/=i;
        ans *= Pow(i,cnt/n);
    }
    if(p!=1){
        if(n == 1)
            ans *= p;
    }
    cout<<ans<<endl;
    return 0;
}


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

int main() 
{ 
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    long long int n,a=0,r=0,w=0,t=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        if(s=="AC")
        a++;
        if(s=="TLE")
        t++;
        if(s=="WA")
        w++;
        if(s=="RE")
        r++;
    }
    cout<<"AC x "<<a<<endl;
    cout<<"WA x "<<w<<endl;
    cout<<"TLE x "<<t<<endl;
    cout<<"RE x "<<r<<endl;
    return 0;
}

Measured memory_bytes: 3656
#include <stdio.h>

// |S|=A+B+1

int main(){
	int A, B;
	char str[20]; // menampung postal code
	bool valid = true; // kita anggap semua postal code AWALNYA itu valid
	scanf("%d %d", &A, &B);	
	scanf("%s", &str); 
	
	
	if(str[A] != '-'){ // cek apakah di index A itu bukan -
		valid = false; // jika bukan, valid menjadi false
	}
	for( int i = 0; str[i] != '\0'; i++){
		if( i != A){ // cek index selain A
			if(str[i] < '0' || str[i] > '9'){ //jika dia di luar rentang 0 sampai 9
				valid = false; // valid menjadi false
				break;// keluar dari loop
			}
		}
	}
	// jika valid adalah true, puts yes, selain itu no
	(valid) ? puts("Yes") : puts("No");	
	return 0;
}

Measured memory_bytes: 1664
n=int(input())
A=list(map(int,input().split()))

L,R=[0]*n,[0]*n
L[0],R[-1]=A[0],A[-1]

from fractions import gcd

for i in range(1,n):
    L[i]=gcd(A[i],L[i-1])
for i in range(n-2,-1,-1):
    R[i]=gcd(A[i],R[i+1])

ans=max([L[-2],R[1]]+[gcd(L[i-1],R[i+1])for i in range(1,n-1)])
print(ans)

Measured memory_bytes: 89952
A=list(input())+["d"]
B=list(input())+["d"]
C=list(input())+["d"]
s=A[0]

while s!="d":
  if s=="a":
    s=A[0]
    del A[0]
    
      
  elif s=="b":
    s=B[0]
    del B[0]
   
  elif s=="c":
    s=C[0]
    del C[0]
    
if len(A)==0:
  print("A")
if len(B)==0:
  print("B")
if len(C)==0:
  print("C")

Measured memory_bytes: 3064
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.next().split("");
        String t = sc.next();
        String concat = "";
        for (int i = 0; i < s.length; i++) {
            concat = s[s.length - 1];
            for (int j = 0; j < s.length - 1; j++) {
                concat += s[j];
            }
            // 一致してたら修了
            if (concat.equals(t)) {
                System.out.println("Yes");
                return;
            }
            // 連結した文字列を分解
            s = concat.split("");
        }
        System.out.println("No");
    }
}


Measured memory_bytes: 26836
import java.util.Scanner;

public class Main {
	private static Scanner sc=new Scanner(System.in);
	private static int alice=sc.nextInt();
	private static int bob=sc.nextInt();
	public static void main(String[] args){
		if(alice==1) alice=14;
		if(bob==1) bob=14;
		if(alice>bob){
			System.out.println("Alice");
		}
		else if(bob>alice){
			System.out.println("Bob");
		}else{
			System.out.println("Draw");
		}
	}
}

Measured memory_bytes: 20820
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
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

N = input()
if N[0] == N[2]:
    print("Yes")
else:
    print("No")


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

int gcd(int x, int y) {
  if(x % y == 0) return y;
  return gcd(y, x % y);
}

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

  int K;
  cin >> K;

  int ans = 0;
  for(int a = 1; a <= K; ++a) {
    for(int b = 1; b <= K; ++b) {
      for(int c = 1; c <= K; ++c) {
        ans += gcd(gcd(a, b), c);
      }
    }
  }

  cout << ans <<endl;

  return 0;
}


Measured memory_bytes: 3640
n,m,x = gets.chomp.split(" ").map(&:to_i)
a = []
n.times do |c|
  a << gets.chomp.split(" ").map(&:to_i)
end

a.sort_by!{|e| e[0] }

skill = Array.new(m)

min = nil

(1..n).each do |i|
  a.combination(i).each do |jmap|
    sum = 0
    skill.fill(0)
    jmap.each do |k|
      sum += k[0]
      m.times do |c|
        skill[c] += k[c+1]
      end
    end
    good = true
    skill.each do |sk|
      if sk < x
        good = false
        break
      end
    end
    if good
      if min.nil?
        min = sum
      else
        if sum < min
          min = sum
        end
      end
    end
  end
end

if min.nil?
  puts("-1")
else
  puts("#{min}")
end


Measured memory_bytes: 14232
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();//A
    int b = sc.nextInt();//B
    if(b % a == 0){//BがAで割り切れるかつまり余りがゼロか
      System.out.println(a + b);//A+Bの表示
    } else {
      System.out.println(b - a);//B-Aの表示
    }
  }
}

Measured memory_bytes: 21716
l,r =map(int, input().split())

if r-l >= 2019:
    print(0)
else:
    ll = []
    for i in range(l, r+1):
        for j in range(l, r+1):
            if i == j:
                pass
            else:
                ll.append(i*j%2019)
    print(min(ll))            

Measured memory_bytes: 147712
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd_(ll a,ll b){if(a%b==0)return b;return gcd_(b,a%b);}
ll lcm_(ll a,ll b){ll c=gcd_(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}


int main(){
  ll N;
  cin >> N;
  vector<ll> A(N+1,10000000);
  FOR(i,0,N) cin >> A[i+1];
  ll k = 1000;
  FOR(i,1,N){
    k = max(k,k%A[i]+(k/A[i])*A[i+1]);
  }
  cout << k << endl;
}



Measured memory_bytes: 3628
#include <iostream>
using namespace std;
int main()
{
    int a,b;
    cin >> a >> b;
    if(a <= 0&&b >= 0)
        cout << "Zero\n";
    else if(a > 0)
        cout << "Positive\n";
    else
        cout << ((b-a)%2==0?"Negative":"Positive") << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;

int n, m, say[N];

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d %d",&n ,&m);
	for(int i = 1; i <= m; i++){
		int u, v;
		scanf("%d %d",&u ,&v);
		say[u]++;
		say[v]++;
	}
	for(int i = 1; i <= n; i++)
		if(say[i] % 2){
			puts("NO");
			return 0;
		}
	puts("YES");
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FASTIO
#define endl "\n"  // Since endl forces a buffer flush which slows down large I/O operations.
#define ff first
#define ss second
#define pb push_back
#define input(c, n) for (int i = 0; i < n; ++i) cin >> c[i];
#define exit_message(s) return 0 * printf(s)
#define show_all(c) for (auto i: c) cout << i << " "; cout << "\n";
#define display(c, a, n) cout << "Displaying array \"" << #c << "\" : \n"; for (int (i) = (a); (i) < (n); ++(i)) cout << (c)[(i)] << " "; cout << "\n";
#define forl(i, a, n) for (int i = (a); (i) < (n); ++(i))
#define dugbe(k) cerr << "-\t> " << #k << " = " << k << "\n";

// What follows is a magical ordered set data structure.
// Supports the following functions:
// find_by_order(int k) - returns k'th smallest element (0-indexed)
// order_of_key(int k) - returns number of elements strictly smaller than k.
using namespace __gnu_pbds;
#define ordered_set tree <ll, null_type, greater_equal <ll>, rb_tree_tag, tree_order_statistics_node_update>

/* TIPS FOR DEBUGGING
 * Check if values are not overflowing (use long long where required)
 * Check if ranges are inclusive or not.
 * Check properly if greedy will work or not before using it.
 * Check EDGE CASES!! Seriously, even in 2B, saving 8 points by being
 * 2 minutes faster will bite you in the ass if you don't make sure
 * it works on edge cases.
 * Keep adding to this list.
*/

using namespace std;
typedef long long ll;
typedef pair<int, int> pr;
typedef pair<ll, ll> prll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pr> vpr;
ifstream in("input.txt");
const ll mod = 1e9 + 7;
const long double eps = 1e-7;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

long long true_rand(long long n)
{
	// Returns a random number between 0 and n - 1 inclusive using mt19937.
    uniform_int_distribution<long long> uid(0, n - 1);
    return uid(rng);
}

ll mod_pow(ll a, ll b)
{
	if (b == 0)
		return 1LL;

	ll res = mod_pow(a, b >> 1);
	res = (res * res) % mod;
	if (b & 1LL)
		res = (res * a) % mod;
	
	return res;
}

const int N = 2e5 + 5, INF = 2e9;
vll Tree;

int32_t main()
{
	#ifdef FASTIO
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);
	#endif
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

	int n;
	cin >> n;

	int k = 1;
	while (k < n)
		k *= 2;
	Tree.assign(k * 2, 0);
 
	vi h(n), a(n);
	forl(i, 0, n)
	{
		cin >> h[i];
	}
	forl(i, 0, n)
	{
		cin >> a[i];
	}

	ll ans = 0;

	for (int i = n - 1; i >= 0; --i)
	{
		// Picking flower i as the first flower.
		// And then choosing the best next flower.

		ll val = 0;
		int l = k + h[i], r = k + n;
		// Querying in range [l, r).
		while (l < r)
		{
			if (l & 1)
				val = max(val, Tree[l]), ++l;
			l >>= 1;
			if (r & 1)
				val = max(val, Tree[r - 1]), --r;
			r >>= 1;
		}
		val += a[i];
		ans = max(ans, val);

		// Update Tree[h[i]] to val.
		int idx = k + h[i] - 1;
		while (idx >= 1)
		{
			Tree[idx] = max(Tree[idx], val);
			idx >>= 1;
		}
	}
	cout << ans << "\n";

	return 0;
}	

Measured memory_bytes: 5888
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N=110;
int tt;
int head[N],to[N*2],nxt[N*2],f[N],dep[N],v[N];
inline int gi() {
    int x=0,o=1;
    char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
inline void dfs(int x,int fa) {
    dep[x]=0;
    for(int i=head[x];i;i=nxt[i])
	if(to[i]!=fa) dfs(to[i],x),dep[x]=max(dep[x],dep[to[i]]+1);
}
inline void solve(int x,int fa,int d) {
    int ch=0;
    for(int i=head[x];i;i=nxt[i])
	if(to[i]!=fa) ++ch,solve(to[i],x,d+1);
    f[d]=max(ch,f[d]);
}
int main() {
    int n,ans=1<<30,tp=0;
    cin>>n;
    for(int i=1;i<n;i++) {
	int x=gi(),y=gi();
	to[++tt]=y,nxt[tt]=head[x],head[x]=tt;
	to[++tt]=x,nxt[tt]=head[y],head[y]=tt;
    }
    for(int i=1;i<=n;i++)
	dfs(i,0),ans=min(ans,dep[i]);
    for(int i=1;i<=n;i++) {
	dfs(i,0);
	if(dep[i]==ans) v[++tp]=i;
    }
    long long sum=-1;
    if(tp==1) {
	++ans;
	cout<<ans<<' ';
	int x=v[1],y;
	solve(x,0,0),sum=1;
	for(int j=0;j<ans-1;j++) sum*=f[j];
	for(int i=head[x];i;i=nxt[i]) {
	    y=to[i];
	    memset(f,0,sizeof(f));
	    solve(x,y,0),solve(y,x,0);
	    long long g=2;
	    for(int j=0;j<ans-1;j++) g*=f[j];
	    sum=min(sum,g);
	}
    }
    else {
	cout<<ans<<' ';
	int x=v[1],y=v[2];
	solve(x,y,0),solve(y,x,0),sum=2;
	for(int j=0;j<ans-1;j++) sum*=f[j];
    }
    cout<<sum;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stack>
#include <cmath>
#include <functional>
#include <set>
#include <string>
#include <stdlib.h>
#include <iomanip>
#include <utility>
 
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i = a;i<=b;i++)
#define ll long long int
#define ii pair<int,int>
#define mp make_pair
#define pb push_back
#define iii pair<ii,int >
#define ff first
#define ss second
#define vi vector<ll>
#define vc vector<char>
 
using namespace std;

const int MOD = (int)1e9+7;
struct Matrix{
	int n;
	vi* arr;	
};
inline Matrix* multiply(Matrix* m1,Matrix* m2){
	int n = m1->n;
	/*

	cout << "first Matrix : " <<endl;
	
	FOR(i,n){
		FOR(j,n){
			cout << m1->arr[i][j] << " ";
		}
		cout << endl;
	}

	cout << "second Matrix : " <<endl;
	
	FOR(i,n){
		FOR(j,n){
			cout << m2->arr[i][j] << " ";
		}
		cout << endl;
	}*/
	Matrix* m3 = new Matrix();
	m3->n = n;
	m3->arr = new vi[n];
	FOR(i,n){
		FOR(j,n){
			ll sum = 0;
			FOR(k,n){
				sum += m1->arr[i][k]*m2->arr[k][j];
				sum %= MOD;
			}
			m3->arr[i].pb(sum);
		}
	}
	
/*
	cout << "final Matrix : " <<endl;
	
	FOR(i,n){
		FOR(j,n){
			cout << m3->arr[i][j] << " ";
		}
		cout << endl;
	}
*/
	
	return m3;
}

Matrix* fxp(Matrix* b,ll k){
	if(k == 1)return b;
	if(k%2 == 0){
		Matrix* mm = fxp(b,k/2);
		mm = multiply(mm,mm);
		/*cout << "final returned Matrix : " <<endl;
		
		FOR(i,mm->n){
			FOR(j,mm->n){
				cout << mm->arr[i][j] << " ";
			}
			cout << endl;
		}*/
		return mm;
	}else{
		return multiply(b,fxp(b,k-1));
	}
}


int main(){
	int n;
	ll k;
	cin >> n;
	cin >> k;
	Matrix* m1 = new Matrix();
	m1->n = n;
	m1->arr = new vi[n];
	FOR(i,n)FOR(j,n){
		int a;
		cin >> a;
		m1->arr[i].pb(a);
	}
	m1 = fxp(m1,k);
	ll sum = 0;
	FOR(i,n){
		FOR(j,n){
			sum += m1->arr[i][j];
			sum %= MOD;
		}
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 3456
def cnt_honest(bit):
    for i in range(n):
        if bit[i] == "1":
            for x, y in hf[i]:
                if bit[x - 1] != str(y):
                    return 0
    return bit.count("1")


n = int(input())
hf = [[] for i in range(n)]

for i in range(n):
    for j in range(int(input())):
        hf[i].append(list(map(int, input().split())))

ans = 0
for i in range(2 ** n):
    ans = max(ans, cnt_honest(format(i, "b").zfill(n)))
print(ans)

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

using namespace std;

int main()
{
	vector<vector<int> > C(3,vector<int>(3));
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			cin >> C[i][j];

	int a,b,c,d,e,f;
	bool flag=false;
	for(a=0;a<=100;a++)
	{
		d=C[0][0]-a;
		e=C[1][0]-a;
		f=C[2][0]-a;
		
		b=C[0][1]-d;
		c=C[0][2]-d;

		bool tmpflag=true;
		
		if(C[1][1]!=b+e)tmpflag=false;
		if(C[1][2]!=c+e)tmpflag=false;
		if(C[2][1]!=b+f)tmpflag=false;
		if(C[2][2]!=c+f)tmpflag=false;

		if(tmpflag)flag=true;
	}
	
	cout << (flag ? "Yes":"No") << endl;

	
}


Measured memory_bytes: 256
//In the name of GOD
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll maxn = 1e5 + 100;
const ll maxm = 1024;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt" , "r+" , stdin) ; freopen("output.txt" , "w+" , stdout);
#define pb push_back
#define Mp make_pair
#define pll pair<ll, ll>
#define F first
#define S second

ll n, q, a[3 * maxn], b[3 * maxn], dp[maxm][maxn];

ll solve(ll v, ll l){
	if(l < 0) return -inf;
	if(v < maxm) return dp[v][l];
	return max(solve(v / 2, l), solve(v / 2, l - b[v]) + a[v]);
}

int main(){
	ll v, l;
	fast_io;
	
	cin >> n;
	for(ll i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
	}
	for(ll i = 1; i < maxm; i++){
		for(ll j = 0; j < maxn; j++){
			dp[i][j] = dp[i / 2][j];
			if(j >= b[i]) dp[i][j] = max(dp[i][j], dp[i / 2][j - b[i]] + a[i]);
		}
	}
	cin >> q;
	for(ll i = 0; i < q; i++){
		cin >> v >> l;
		cout << solve(v, l) << '\n';
	}
	
	return 0;
}


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

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SP << " " <<

LL mod = 1000000007;

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

  LL N;
  cin >> N;
  vector<LL> W(N);
  LL sum = 0;
  REP(i, N)
  {
    cin >> W[i];
    sum += W[i];
  }

  LL sum2 = 0;

  LL min = mod;

  REP(i,N-1){
    sum2 += W[i];
    sum -= W[i];
    if(min>abs(sum-sum2)){
      min = abs(sum - sum2);
    }
  }
  cout << min << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define INF 2100000000
#define LLINF 10000000000000000ll
#define MOD 1000000007

bool dbgflag = false; //debug

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

  int n;
  cin >> n;

  vector<int> color(2*n-1);
  color[n-1] = -INF;
  for (int i = 1; i < n; i++) {
    color[n+i-1] = INF;
    color[n-i-1] = -1 * INF;
  }
  
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    if (dbgflag) cout <<"a " << a << endl;
    *(lower_bound(color.begin(), color.end(), a) - 1) = a;
  }

  if (dbgflag) {
    for (int i = 0; i < color.size(); i++) {
      cout << color[i] << endl;
    }
  }

  cout << (int)(lower_bound(color.begin(), color.end(), INF) - upper_bound(color.begin(), color.end(), -1*INF)) << endl;
}


Measured memory_bytes: 1024
#include<stdio.h>
int main()
{
   int a,b,c,d,t,m;
   scanf("%d %d %d %d",&a,&b,&c,&d);
   t = (a+d-1)/d;
   m = (c+b-1)/b;
   if(t >= m){
     printf("Yes\n");
   }
   else printf("No\n");
}


Measured memory_bytes: 1624
#include <iostream>
#include <iomanip>
#include <string>
#include <stack>

using namespace std;

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,j) for(int i=0;i<j;i++)

int main(){

	int N, x;
	while(1){

		int sum = 0;
		
		cin >> N >> x;
		if(N == 0 && x == 0){
			break;
		}
		
		REP(i,1,N-1){
			REP(j,i+1,N){
				REP(k,j+1,N+1){
					if(x == i + j + k){
						sum++;
					}
				}
			}
		}
		cout << sum << "\n";
	}

	return 0;
}

Measured memory_bytes: 1160