akhauriyash/Code-Regression huggingface dataset:
def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count


import sys
sys.setrecursionlimit(10**6)


N=10**9 + 7
n=int(input())
g=[[] for _ in range(n+5)]
for _ in range(n-1):
    a,b=map(int,input().strip().split(" "))
    g[a-1].append(b-1)
    g[b-1].append(a-1)
dpr=[-1 for _ in range(n+5)]
dpb=[-1 for _ in range(n+5)]

def dfs(v,p):
    if dpr[v]!=-1:
        return
    if len(g[v])==1 and g[v][0]==p:
        dpr[v]=1
        dpb[v]=1
        return
    valr=1
    valb=1
    for c in g[v]:
        if c==p:
            continue
        dfs(c,v)
        valr=(valr*((dpr[c]+dpb[c])%N))%N
        valb=(valb*(dpr[c]))%N
    dpr[v]=valr
    dpb[v]=valb
    return
dfs(0,-1)
print((dpr[0]+dpb[0])%N)

















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

#define rep(i,n) for(int i = 0; i < n; i++)
#define MOD 1000000007

int main()
{
  int N;
  cin >> N;
  vector<long long int> T(N), A(N), T_f(N), A_f(N);
  rep(i,N)
    {
      cin >> T[i];
      T_f[i] = 0;
      A_f[i] = 0;
    }
  rep(i,N)
    {
      cin >> A[i];
    }
  if(N == 1)
    {
      if(A[0] == T[0])
	{
	  cout << "1" << endl;
	}else{
	cout << "0" << endl;
      }
      return 0;
    }
  if(T[N-1] != A[0])
    {
      cout << "0" << endl;
      return 0;
    }
  
  for(int i = 1; i < N; i++)
    {
      if(T[i-1] == T[i])
	{
	  T_f[i] = 1;
	}
      if(T[i-1] > T[i])
	{
	  cout << "0" << endl;
	  return 0;
	}
    }
  for(int i = N-2; i >= 0; i--)
    {
      if(A[i] == A[i+1])
	{
	  A_f[i] = 1;
	  continue;
	}
      if(A[i] < A[i+1])
	{
	  cout << "0" << endl;
	  return 0;
	}
    }
  for(int i = 1; i < N-1; i++)
    {
      if(T_f[i] == 0 && A_f[i] == 1)
	{
	  if(T[i] > A[i])
	    {
	      cout << "0" << endl;
	      return 0;
	    }
	}
      if(T_f[i] == 1 && A_f[i] == 0)
	{
	  if(T[i] < A[i])
	    {
	      cout << "0" << endl;
	      return 0;
	    }
	}
      if(T_f[i] == 0 && A_f[i] == 0)
	{
	  if(T[i] != A[i])
	    {
	      cout << "0" << endl;
	      return 0;
	    }
	}
    }
  long long int ans = 1;
  for(int i = 1; i < N; i++)
    {
      if(T_f[i] == 1 && A_f[i] == 1)
	{
	  ans *= min(T[i], A[i]);
	  ans %= MOD;
	}
    }
  /*
  rep(i, N)
    {
      cout << T_f[i];
    }
  cout << endl;
  rep(i, N)
    {
      cout << A_f[i];
    }
  cout << endl;
  */
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
long long arr[1000000];
int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);   
    long long h1,h2,m1,m2,i,j,k,x,y,z;
    cin>>h1>>m1>>h2>>m2>>k;
    x=h1*60+m1;
    y=h2*60+m2;
    z=y-x-k;
    if (z<0)
    {
    	cout<<0<<endl;
	}
	else
	{
		cout<<z<<endl;
	}
}

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

using i64 = int64_t;

#define rep(i, x, y) for (i64 i = i64(x), i##_max_for_repmacro = i64(y); i < i##_max_for_repmacro; ++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf = 1.01e9;
const i64 inf64 = 4.01e18;
const double eps = 1e-9;

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "[";
    for (const auto &v : vec) {
        os << v << ",";
    }
    os << "]";
    return os;
}

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

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

template<typename T, size_t size> void fill(T (&ary)[size], const T& val){
    fill_n((T*)ary, size, val);
}

void solve() {
    //const i64 mod = 1'000'000'007;

    char b;
    cin >> b;

    switch(b){
        case 'A':
            cout << "T" << endl;
            break;
        case 'C':
            cout << "G" << endl;
            break;
        case 'G':
            cout << "C" << endl;
            break;
        case 'T':
            cout << "A" << endl;
            break;
    }
}

int main() {
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String a = sc.next();
		String b = sc.next();

		if ("H".equals(a) && "H".equals(b) || "D".equals(a) && "D".equals(b)) {
			System.out.println("H");
		} else {
			System.out.println("D");
		}

		sc.close();

	}

}

Measured memory_bytes: 35736
#!/usr/bin/env python3
import sys


def solve(N: int):
    ans = 0
    for a in range(1, N):
        bb = N // a
        cc = N % a
        ans += bb - (1 if cc == 0 else 0)
    return ans


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    print(solve(N))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()


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

int selectionSort(int values[], int n) {
  int switch_count = 0;
  for (int i = 0; i < n; i++) {
    int minj = i;
    for (int j = i; j < n; j++) {
      if (values[j] < values[minj]) {
        minj = j;
      }
    }
    if (i != minj) {
      swap(values[i], values[minj]);
      switch_count++;
    }
  }
  return switch_count;
}

int main() {
  int n;
  cin >> n;
  int values[n];

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

  int switch_count = selectionSort(values, n);

  for (int j = 0; j < n - 1; j++) {
    cout << values[j] << " ";
  }
  cout << values[n - 1] << endl;
  cout << switch_count << endl;

}



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

int main()
{
    int n;
    cin >> n;
    
    int arrSize = n * 3;
    unsigned long long* arr = new unsigned long long[arrSize];
    
    for(int i = 0; i < arrSize; i++)
    {
        cin >> arr[i];
    }
    
    sort(arr, arr + arrSize);
    reverse(arr, arr + arrSize);
    
    unsigned long long sum = 0;
    
    for(int i = 0; i < n; i++)
    {
        int index = i * 2 + 1;
        sum += arr[index];
    }
    
    cout << sum << endl;
    
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  bool is_prime[1000000];
  REP1(i, 999999) is_prime[i] = true;
  is_prime[0] = is_prime[1] = false;
  for (int i = 2; i * i <= 999999; ++i) {
    if (is_prime[i]) {
      for (int j = 2; i * j <= 999999; ++j) is_prime[i * j] = false;
    }
  }
  int sum[1000000];
  sum[0] = 0;
  REP1(i, 999999) sum[i] = sum[i - 1] + is_prime[i];
  int n;
  while (cin >> n) cout << sum[n] << endl;
  return 0;
}


Measured memory_bytes: 7948
from collections import deque
import bisect

n = int(input())
a = [int(input()) for _ in range(n)]


b = deque([])

for ai in a:
    if len(b) == 0:
        b.append(ai)
    else:
        if ai <= b[0]:
            b.appendleft(ai)
        else:
            index = bisect.bisect_left(b, ai)
            b[index-1] = ai

print(len(b))


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

int main(){
  string s;
  long long k;
  cin >> s >> k;
  if(s == string(s.size(),s.at(0))){
    cout << s.size()*k/2 << endl;
    return 0;
  }
  
  long long ans =0;
  string t = s+s;
  long long x=0,y=0;
  int n=s.size();
  for(int i=0;i<n-1;i++){
    if(s.at(i) == s.at(i+1)){
      s.at(i+1) = '#';
      x++;
    }
  }
  for(int i=0;i<t.size()-1;i++){
    if(t.at(i) == t.at(i+1)){
      t.at(i+1) = '#';
      y++;
    }
  }
  ans = x + (y-x)*(k-1);
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    //nextLineとnextを同時に使ったら死ぬ
    val sc = new Scanner(System.in)
    val s = Array.fill(3)(sc.next())
    println(Array(s(0)(0), s(1)(1), s(2)(2)).mkString)
  }
  def debug(args: Any*): Unit = {
    Console.err.println(args.mkString(" "))
  }
}


Measured memory_bytes: 27464
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 200000;
int arr[maxn];
vector<int> vec;
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&arr[i]);
		vec.push_back(arr[i]);
	}
	sort(vec.begin(),vec.end());
	float mid = (vec[n/2]+vec[n/2-1])/2.00;
	for(int i=0;i<n;i++){
		if((float)arr[i] < mid){
			///in left
			printf("%d\n",vec[n/2]);
		}
		else{
			printf("%d\n",vec[n/2-1]);
		}
	}
    return 0;
}

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);
    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

// get<K>(tuple型の変数)

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */


const long double pi = acos(-1);
const long double eps = 0.000000001;

long double a, b, x;

long double f(long double theta){
    if(theta > pi / 2.0 - eps) return 0;
    if(a*tan(theta) <= b) return a * a * b - a * a * a * tan(theta) / 2;
    else return a * b * b / tan(theta) / 2;
}

void input(){
    cin >> a >> b >> x;
}

void solve(){
    input();
    long double ok = pi / 2.0;
    long double ng = 0.0;
    for(int _=0; _<100000; ++_){
        long double mid = (ok + ng) / 2.0;
        (f(mid) < x? ok:ng) = mid;
    }
    cout << setprecision(13) << ok * 180 / pi << endl;
}

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

    solve();
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
static const int MAX=100000;
static const int INFTY=2000000000;
class Edge{
    public:
        int t,w;
        Edge();
        Edge(int t,int w):t(t),w(w){}
};

vector<Edge> G[MAX];
int n,d[MAX];

void bfs(int s){
    for(int i=0;i<n;i++) d[i]=INFTY;
    queue<int> Q;
    Q.push(s);
    d[s]=0;
    int u;
    while(!Q.empty()){
        u=Q.front();
        Q.pop();
        for(int i=0;i<G[u].size();i++){
            Edge e=G[u][i];
            if(d[e.t]==INFTY){
                d[e.t]=d[u]+e.w;
                Q.push(e.t);
            }
        }
    }
}
    
void solve(){
    bfs(0);
    int maxv=0;
    int tgt=0;
    for(int i=0;i<n;i++){
        if(d[i]==INFTY)continue;
        if(maxv<d[i]){
            maxv=d[i];
            tgt=i;
        }
    }
    bfs(tgt);
    maxv=0;
    for(int i=0;i<n;i++){
        if(d[i]==INFTY)continue;
        maxv=max(maxv,d[i]);
    }
    cout<<maxv<<"\n";
}
int main(){
    int s,t,w;
    cin>>n;
    for(int i=0;i<n-1;i++){
        cin>>s>>t>>w;
        G[s].push_back(Edge(t,w));
        G[t].push_back(Edge(s,w));
    }
    solve();
    return 0;
}



Measured memory_bytes: 9920
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
#define REP(i,n) for (lint i = 0; i < (n); i++)
#define REP1(i,n) for (lint i = 1; i < (n); i++)

lint H, N;
vector<lint> A;

int main(void){
    cin >> H >> N;
    REP (i, N ){
        lint a;
        cin >> a;
        A.push_back(a);
    }
    lint dmg_sum = accumulate(A.begin(), A.end(), 0);
    (dmg_sum >= H) ? cout << "Yes" << endl : cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 1400
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1<<30;
vvi fil;
int r,l;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int main(){
	int w,h;
	while(cin>>w>>h,w+h){
		int n;
		cin>>n;
		vvi in(n,vi(4));
		vi x,y;
		rep(i,n)rep(j,4)cin>>in[i][j];
		rep(k,2)rep(i,n)for(int d=-1;d<=1;d++){
			int X=in[i][k*2]+d,Y=in[i][k*2+1]+d;
			if(0<=X&&X<=w)x.pb(X);
			if(0<=Y&&Y<=h)y.pb(Y);
		}
		sort(all(x));sort(all(y));
		x.erase(unique(all(x)),x.end());
		y.erase(unique(all(y)),y.end());
		r=x.size()-1,l=y.size()-1;
		fil=vvi(r,vi(l));
		rep(i,n){
			int a=find(all(x),in[i][0])-x.begin();
			int b=find(all(y),in[i][1])-y.begin();
			int c=find(all(x),in[i][2])-x.begin();
			int d=find(all(y),in[i][3])-y.begin();
			loop(j,a,c)loop(k,b,d)
				fil[j][k]=1;
		}
		int co=0;
//		rep(i,r){rep(j,l)cout<<fil[i][j];cout<<endl;}
		rep(i,r)rep(j,l)if(fil[i][j]==0){
			co++;
			fil[i][j]=1;
			queue<pii>q;
			q.push(pii(i,j));
			while(!q.empty()){
				pii p=q.front();
				q.pop();
				rep(k,4){
					int nx=p.first+dx[k];
					int ny=p.second+dy[k];
					if(nx<0||ny<0||nx>=r||ny>=l)continue;
					if(fil[nx][ny]==0){
						fil[nx][ny]=1;
						q.push(pii(nx,ny));
					}
				}
			}
		}
		cout<<co<<endl;
	}
}

Measured memory_bytes: 43244
import java.util.Scanner;
import java.util.Arrays;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int h = sc.nextInt();
    int n = sc.nextInt();
    boolean condition = false;
    int[] T = new int[n];
    for (int i = 0; i < n; i++) {
      h -= sc.nextInt();
      if (h <= 0) {
        condition = true;
        break;
      }
    }
    System.out.println(condition? "Yes":"No");
  }
}

Measured memory_bytes: 49476
#include <vector>
#include <map>
#include <string>
#include <iostream>
#include <cmath>
#include <random>
#include <cctype>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define MK make_pair
#define PB push_back
#define VI vector<int>
#define VII vector<int,int>
#define MSI map<string,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define W1 while(1);
const int MOD = 1000000007;
int main()
{
	string c;
	cin >> c;
	if (c.at(0) == 'a' || c.at(0) == 'e' || c.at(0) == 'i' || c.at(0) == 'o' || c.at(0) == 'u')
	{
		cout << "vowel" << endl;
	}
	else
	{
		cout << "consonant" << endl;
	}
	return 0;
}

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

int main() {
	int n;
	cin >> n;
	vector<tuple<string, int, int>>a;
	for (int i = 1;i <= n;++i) {
		string s;
		int p;
		cin >> s >> p;
		p = -p;
		a.push_back(tie(s, p, i));
	}
	sort(a.begin(), a.end());
	for (int i = 0;i < n;++i) {
		cout << get<2>(a[i]) << endl;
	}
}

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

int main() {
	long long N; cin >> N;
	long long ans = 999999999999;
	for (long long i = 1; i <= sqrt(N); i++) {
		if (N % i == 0) {
			long long S = N / i;
			ans = min(ans, S + i);
		}
	}
	cout << ans - 2 << endl;
 }

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

int cnt(int p, vector<long long> &q){
    int as;
    int le = 0;
    int ri = q.size() - 1;
    int mid = (le + ri) / 2;
    if (p < q.at(0)){
        return 0;
    }
    else if (p >= q.at(ri)){
        return ri + 1;
    }
    while (p < q.at(mid) || p >= q.at(mid + 1)){
        if (p >= q.at(mid + 1)){
            le = mid;
        }
        else{
            ri = mid;
        }
        mid = (le + ri) / 2;
    }
    return mid + 1;
}

int main(){
    int n;
    cin >> n;
    vector<long long> a(n);
    vector<long long> b(n);
    vector<long long> c(n);
    rep(i, n){
        cin >> a.at(i);
    }
    rep(k, n){
        cin >> b.at(k);
    }
    rep(j, n){
        cin >> c.at(j);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    long long ans = 0;
    vector<long long> bb(n+1);
    bb.at(n) = 0;
    for (int g = 0; g < n; g++){
        bb.at(g) = n - cnt(b.at(g), c);
    }
    for (int h = n - 2; h >=0; h--){
        bb.at(h) += bb.at(h+1);
    }
    for (int l = 0; l < n; l++){
        ans += bb.at(cnt(a.at(l), b));
    }
    cout << ans << endl;
}

Measured memory_bytes: 3328
#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    if(n==1)
    {
        printf("Hello World\n");
    }
    if(n==2)
    {
        int a,b,sum;
        scanf("%d%d",&a,&b);
        sum=a+b;
        printf("%d\n",sum);
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,x;
  cin>>n>>x;
  int mi =1<<30;
  int ans =n;
  for(int i=0;i<n;i++){
    int m;
    cin>>m;
    mi = min(mi,m);
    x -=m;
  }
  cout << ans + x/mi;
}

Measured memory_bytes: 256
/* Don't try to copy it!
                    nhi too,
                         goli maar ke cheed bana dunga...;););)
 
                 
    _/﹋\_
    (҂`_´)
    <,︻╦╤─҉- - - - - - - - => - => - =>
    _/﹋\_
                
*/
 
#include "bits/stdc++.h"
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long int
#define pb push_back
#define f(a) for(ll i = 0;i<a;i++)
#define rep(i,a,b) for(ll i = a;i<b;i++)
#define rrep(i,a,b) for(ll i = a;i>b;i--)
#define vll vector<ll>
#define T ll t; cin>>t; while(t--)
#define freeopen freopen("input.txt","r",stdin);
#define freeclose freopen("output.txt","w",stdout);
#define MOD 1000000007
using namespace std;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); }
ll n,m;
vll v[100001];
ll dp[100001];
ll lp(ll p)
{
    if(v[p].size()==0)
        return 0;
    if(dp[p]!=-1)
        return dp[p];
    ll ans=-1;
    for(ll i=0;i<v[p].size();i++)
    {
        ans=max(ans,1+lp(v[p][i]));
    }
    dp[p]=ans;
    return dp[p];
}
main()
{
    //ll n,m;
    cin>>n>>m;
    for(ll i=0;i<m;i++)
    {
        ll x,y;
        cin>>x>>y;
        x--;
        y--;
        v[x].pb(y);
    }

    ll ans=-1;
    memset(dp,-1,sizeof(dp));
    for(ll i=0;i<n;i++)
    {
        ans=max(ans,lp(i));
    }

    cout<<ans;

}



Measured memory_bytes: 11844
#include "bits/stdc++.h"

using namespace std;
const size_t mv = 1e9 + 7;

int cost(vector<string> vs)
{
    int ns = vs.size();
    if (!ns) return 0;

    int slen = vs[0].size();
    vector<vector<size_t> > cost(ns, vector<size_t>(slen, 0));

    for (int i = 1; i < slen; ++i) if (vs[0][i] == '.') cost[0][i] = 1; else break;
    for (int i = 1; i < ns; ++i) if (vs[i][0] == '.') cost[i][0] = 1; else break;

    for (int i = 1; i < ns; ++i)
    {
        for (int j = 1; j < slen; ++j)
        {
            if (vs[i][j] == '.')
            {
                cost[i][j] = (cost[i][j-1] + cost[i-1][j]) % mv;
            }
        }
    }

    return cost[ns-1][slen-1];
}

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<string> vs;
    string s;
    int n, l; cin >> n >> l;
    for (int i = 0; i < n; ++i) { cin >> s; vs.push_back(s); }
    cout << cost(vs) << endl;
    return 0;
}


Measured memory_bytes: 10240
n = gets.to_i
t = 0
h = 0
for i in 0..n-1
	a, b = gets.split
	if (a <=> b) == 1
		t += 3
	elsif (a <=> b) == -1
		h += 3
	else
		t += 1
		h += 1
	end
end
puts "#{t} #{h}"

Measured memory_bytes: 8656
#include <bits/stdc++.h>
#include <vector> 
# include <cstdint>
#define FOR(i,l,r) for(int i=(l);i<(r);++i)
#define RFOR(i,l,r) for(int i=(l);i>=(int)(r);i--)
#define rep(i,n)  FOR(i,0,n)
#define rrep(i,n)  RFOR(i,n-1,0)

// #define int long long
using namespace std;
const int MX = 1e6;
const int inf = 1e9;
const int mod = 1e9+7;
using P = pair<int, int>;
using ll = long long;
vector<int> to[100005];
int cost[100005];

signed main(){
    int n;
    cin >> n;
    
    if(n%2==0)cout << n << endl;
    else cout << n*2 << endl;

    
    return 0;
}



Measured memory_bytes: 2560
#include "bits/stdc++.h"

using namespace std;

#define COUNTOF(array) (sizeof(array) / sizeof(array[0]))
#define OUT(P) cout << (P) << endl
#define OUT2(P1, P2) cout << (P1) << " " << (P2) << endl
#define PRINT_ARRAY(P) for(int i=0; i<P.size(); i++) cout << P[i] << endl;

// integerの各桁を足す
int sum_digits(int num);

int main() {
    double a, b;    
    cin >> a >> b;
    cout << ceil((a + b) / 2.0) << endl;
    return 0;
}

/******************************/
/***** DECRARED FUNCTIONS *****/
/******************************/

// integerの各桁を足す
int sum_digits(int num) {
    int rtn = 0;
    string num_str = to_string(num);
    for(int i=0; i<num_str.size(); i++) {
        rtn += num_str[i] - '0';
    }   
    return rtn;
}



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


public class Main {
    static final long INF = (long) 1e17;
    static final int max = (int) (1e5 + 1);

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = sc.nextInt();
        int W = sc.nextInt();
        int[] w = new int[n];
        int[] v = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        long[] dp = new long[max];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        long ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = max - 1; j >= v[i]; j--) {
                dp[j] = Math.min(dp[j], w[i] + dp[j - v[i]]);
                if (dp[j] <= W) {
                    ans = Math.max(ans, j);
                }
            }
        }
        out.println(ans);
        out.flush();
        out.close();

    }


    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream system) {
            br = new BufferedReader(new InputStreamReader(system));
        }

        public Scanner(String file) throws Exception {
            br = new BufferedReader(new FileReader(file));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

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

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

        public char nextChar() throws IOException {
            return next().charAt(0);
        }

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

        public boolean ready() throws IOException {
            return br.ready();
        }

        public void waitForInput() throws InterruptedException {
            Thread.sleep(3000);
        }

        public int[] nextIntArray(int n) throws IOException {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

    }
}

Measured memory_bytes: 21844
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define MMP(a, b, c) make_pair(make_pair(a, b), c)
#define MAX 1000000000
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483648
#define INT_MAX 2147483647
#define LL_MIN -9223372036854775808
#define LL_MAX 9223372036854775807
#define PI 3.14159265359

int main(){
    iostream::sync_with_stdio(false);
    
    int H,W,N;
    cin >> H >> W >> N;
    swap(W,H);
    vector<int> jama[200000];
    set<pair<int,int> > ojama;
    for(int i=0; i<N; i++){
        int x,y;
        cin >> x >> y;
        x--; y--;
        jama[y].push_back(x);
        ojama.insert(MP(x,y));
    }
    for(int i=0; i<H; i++){
        jama[i].push_back(W);
        sort(jama[i].begin(), jama[i].end());
    }

    int ans = INT_MAX;
    int X = 0; int Y = 0;
    while(Y < H && X < W){
        if(ojama.count(MP(X,Y)) == 1) break;
        int tmp = *upper_bound(jama[Y].begin(), jama[Y].end(), X);
        ans = min(ans, tmp);
        if(ojama.count(MP(X+1,Y)) == 1) break;
        X++;
        if(ojama.count(MP(X,Y+1)) == 0) Y++;
    }
    cout << ans << endl;
    
    return 0;
}


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

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

int main()
{
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>> p(m);
    rep(i,m) cin>> p[i].first >> p[i].second;
    rep(x,1000)
    {
        int keta = 1;
        int nx = x/10;
        vector<int> d(1,x%10);
        while(nx)
        {
            keta++;
            d.push_back(nx%10);
            nx /= 10;
        }
        if(keta != n)continue;
        bool ok = true;
        reverse(d.begin(),d.end());
        rep(i,m)
        {
            if(d[p[i].first - 1] != p[i].second)ok = false;
        }
        if(ok)
        {
            cout<<x<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long int ll;
ll dx[4]={-1,0,1,0};
ll dy[4]={0,1,0,-1};
ll a[403][403];
string s[403];
void dfs(ll y,ll x,ll n,ll w,ll h){
        a[y][x]=n;
        for(int i=0;i<4;i++) {
                ll nx=x+dx[i]; ll ny=y+dy[i];
                if(nx<0||ny<0||nx>=w||ny>=h) continue;
                if(a[ny][nx]!=0) continue;
                if(s[y][x]=='#') {
                  if(s[ny][nx]!='.') continue;
                }
                if(s[y][x]=='.') {
                  if(s[ny][nx]!='#') continue;
                }
                dfs(ny,nx,n,w,h);
        }
      return;//もし移動し続けてtrueがでなかったらfalse
}
int main(){
ll h,w;
cin >>h>>w;
for(ll i=0;i<h;i++) cin >>s[i];
ll n=1;
for(ll i=0;i<h;i++){
  for(ll j=0;j<w;j++){
    if(a[i][j]==0) {
      dfs(i,j,n,w,h);
      n++;
    }
  }
}
ll aa[n],bb[n],k=0;
for(ll i=0;i<n;i++){
  aa[i]=0;
  bb[i]=0;
}
for(ll i=0;i<h;i++){
  for(ll j=0;j<w;j++){
    if(a[i][j]!=0){
      if(s[i][j]=='#') aa[a[i][j]-1]++;
      if(s[i][j]=='.') bb[a[i][j]-1]++;
    }
  }
}
ll ans=0;
for(ll i=0;i<n;i++){
  ans+=(aa[i]*bb[i]);
}
cout <<ans<<endl;
}


Measured memory_bytes: 16768
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

ll gcd(ll n, ll m){
    if(n % m == 0) return m;
    return gcd(m, n % m);
}

int main()
{
    ll prime[100000] {0};
    bool ifp[1000002];
    for(ll i = 0; i <= 1000000; i++) ifp[i] = true;
    ll p = 0;
    ifp[0] = ifp[1] = false;
    for(ll i = 2; i <= 1000000; i++){
        if(ifp[i]){
            prime[p++] = i;
            for(ll j = 2 * i; j <= 1000000; j+= i) ifp[j] = false;
        }
    }
    ll a, b;
    cin >> a >> b;
    ll g = gcd(a, b);
    ll ans = 1;
    for(ll i = 0; i < p; i++){
        if(g % prime[i] == 0){
            ans++;
            while(g % prime[i] == 0) g /= prime[i];
        }
    }
    if(g != 1) ans++;
    cout << ans << endl;
}

Measured memory_bytes: 2176
#include<stdio.h>
char t[100];
int c(char t){
	if(t=='y'||t=='u'||t=='i'||t=='o'||t=='p'||t=='h'||t=='j'||t=='k'||t=='l'||t=='n'||t=='m')return 1;
	return 0;
}
int main(){
	while(1){
		scanf("%s",t);
		if(t[0]=='#')return 0;
		int now=c(t[0]);
		int ret=0;
		for(int i=1;t[i];i++){
			int p=c(t[i]);
			if(now!=p)ret++;
			now=p;
		}
		printf("%d\n",ret);
	}
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

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

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

template<class T=ll>struct Graph{
	int n;
	vector<vector<tuple<ll,T>>>edge;
	Graph(int N=1):n(N){edge.resize(n);}
	void add(ll f,ll t,T c,bool d=false){
		edge[f].emplace_back(t,c);
		if(!d)edge[t].emplace_back(f,c);
	}
	void view(){
		rep(i,n)for(auto&e:edge[i])
			puta(i,"=>",get<0>(e),", cost :",get<1>(e));
	}
};

template<class T=ll>struct BellmanFord:Graph<T>{
	using Graph<T>::Graph;
	BellmanFord(int N=1):Graph<T>::Graph(N){}
	const T mval=numeric_limits<T>::max()/2;
	vector<T>dist(ll s){
		vector<T> ret(this->n,mval);
		ret[s]=0;
		rep(i,2*this->n){
			rep(f,this->n)for(auto&e:this->edge[f]){
				ll t; T c; tie(t,c)=e;
				if(ret[f]!=mval && chmin(ret[t],ret[f]+c) && i+1>=this->n){
					ret[t]=-mval;
				}
			}
		}
		return ret;
	}
	T dist(ll s,ll t){return dist(s)[t];}
};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,m,p;
	cin>>n>>m>>p;
	BellmanFord<ll> g(n);
	rep(i,m){
		ll a,b,c;
		cin>>a>>b>>c;
		a--;b--;
		g.add(a,b,-(c-p),true);
	}
	ll ans=g.dist(0,n-1);
	ll out=0;
	if(ans==-4611686018427387903)out=-1;
	else if(ans>0)out=0;
	else out=-ans;
	cout<<out<<endl;;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define COUT(x) cout<<(x)<<"\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, n) for(int i=0;i<n;i++)
#define YES(x) cout<<(x?"YES":"NO")<<"\n"
#define Yes(x) cout<<(x?"Yes":"No")<<"\n"
#define dump(x) cout<<#x<<" = "<<(x)<<"\n"
#define endl "\n"
using G = vector<vector<int>>;
using M = map<int,int>;
using P = pair<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int,vector<int>,greater<int>>;
using V = vector<int>;
using ll = unsigned long long;
template<class T>bool CHMAX(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool CHMIN(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  IOS;
  int n; cin >> n;
  ll a[n];
  ll ans = 1;

  REP(i,n) {
    cin >> a[i];
    if (a[i] == 0) {
      COUT(0); return 0;
    }
  }

  REP(i,n) {
    if (a[i] > 1000000000000000000 / ans) {
      COUT(-1);
      return 0;
    }
    ans *= a[i];
  }

  if (ans > 1e18) {
    COUT(-1);
  } else {
    COUT(ans);
  }

  return 0;
}

Measured memory_bytes: 4436
/*
ID: espr1t
TASK: 
KEYWORDS: 
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;
FILE* in = stdin; FILE* out = stdout;

const int MAX = 1001;
const int MOD = 1000000007;

int n, m;
int a[MAX][MAX];
int limR[MAX], whichR[MAX * MAX], avR[MAX];
int limC[MAX], whichC[MAX * MAX], avC[MAX];
int cnt[MAX * MAX];
vector < pair <int, int> > where[MAX * MAX];

int main(void) {
	// in = fopen("D.in", "rt");
	
	memset(whichR, -1, sizeof(whichR));
	memset(whichC, -1, sizeof(whichC));
	
	fscanf(in, "%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
	    fscanf(in, "%d", &limR[i]);
	    if (whichR[limR[i]] != -1) {
	        fprintf(out, "0\n");
	        return 0;
        }
        whichR[limR[i]] = i;
    }
	for (int i = 0; i < m; i++) {
	    fscanf(in, "%d", &limC[i]);
	    if (whichC[limC[i]] != -1) {
	        fprintf(out, "0\n");
	        return 0;
        }
        whichC[limC[i]] = i;
    }
    
	for (int row = 0; row < n; row++) {
	    for (int col = 0; col < m; col++) {
	        cnt[min(limR[row], limC[col])]++;
	        where[min(limR[row], limC[col])].push_back(make_pair(row, col));
        }
    }
    
    int ans = 1;
    int available = 0;
    for (int num = n * m; num >= 1; num--) {
        available += cnt[num];
        for (int i = 0; i < (int)where[num].size(); i++) {
            avR[where[num][i].first]++;
            avC[where[num][i].second]++;
        }
        // Has predefined position
        if (whichR[num] != -1 && whichC[num] != -1) {
             avR[whichR[num]]--;
            avC[whichC[num]]--;
            available--;
            continue;
        }
        // Has predefined row or column
        if (whichR[num] != -1 || whichC[num] != -1) {
            int positions = 0;
            if (whichR[num] != -1) {
                positions = avR[whichR[num]]--;
            } else {
                positions = avC[whichC[num]]--;
            }
//            fprintf(stderr, "%d has predefined row or column with %d options.\n", num, positions);
            ans = ((long long)ans * positions) % MOD;
            available--;
            continue;
        }
//        fprintf(stderr, "%d has %d choices.\n", num, available);
        if (available == 0) {
            ans = 0;
            break;
        }
        ans = ((long long)ans * available) % MOD;
        available--;
    }
	fprintf(out, "%d\n", ans);
	
	return 0;
}

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

#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

vector<vector<ll>> g;

vector<bool> seen;
vector<ll> ans;
const long long NIL = -1;
deque<ll> todo;

int main() {
  ll n, m;
  cin >> n >> m;
  g.resize(n);
  seen.resize(n);

  ans.resize(n, NIL);

  for (long long i = 0; i < m; i++) {
    ll a, b;
    cin >> a >> b;
    a--;
    b--;

    g.at(a).push_back(b);
    g.at(b).push_back(a);
  }

  todo.push_back(0);
  while (!todo.empty()) {
    ll v = todo.front();
    todo.pop_front();

    if (seen.at(v)) {
      continue;
    }

    for (auto x : g.at(v)) {
      if (ans.at(x) == NIL) {
        ans.at(x) = v + 1;
        todo.push_back(x);
      }
    }
  }

  if (find(seen.begin(), seen.end(), false) == seen.end()) {
    cout << "No" << endl;
    return 0;
  }
  cout << "Yes" << endl;
  for (long long i = 1; i < n; i++) {
    cout << ans.at(i) << endl;
  }
}


Measured memory_bytes: 12860
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	int a, b;
	int c;
	scanf("%d %d", &a, &b);
	c = (a + b) > (a - b) ? (a + b) : (a - b);
	c = c > (a * b) ? c : (a * b);
	printf("%d\n", c);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
  string divide[4]={"dream","dreamer","erase","eraser"};
int main(){
    string s;
    cin>>s;
    reverse(s.begin(),s.end());
    for(int i=0;i<4;i++)reverse(divide[i].begin(),divide[i].end());
    bool can=true;
    for(int i=0;i<s.size();){
        bool can2=false;
        for(int j=0;j<4;j++){
            string d=divide[j];
            if(s.substr(i,d.size())==d){
                can2=true;
                i+=d.size();
            }
        }
        if(!can2){
            can=false;
            break;
        }
    }
    if(can){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }

}

Measured memory_bytes: 512
N = int(input())
XL = []
for i in range(N):
  XL.append(list(map(int, input().split())))
XL.sort()

target = 0
sum = N
for i in range(N-1):
  if (XL[target][0] + XL[target][1]) > (XL[i+1][0] - XL[i+1][1]):
    if (XL[target][0] + XL[target][1]) >= (XL[i+1][0] + XL[i+1][1]):
      target = i + 1
    sum = sum-1
  else:
    target = i + 1
    
print(sum)
  

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

int len[] = {5, 7, 5, 7, 7};
std::vector< std::string > w(40);

bool check(int start, int n) {
    int i = start, k;
    for(k = 0; k < 5; ++k) {
        int rest = len[k];

        if(i >= n) return false;
        while(i < n && rest > 0) {
            rest -= w[i].length();
            ++i;
        }
        if(rest < 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    int i;
    while(std::cin >> n, n != 0) {
        for(i = 0; i < n; ++i) {
            std::cin >> w[i];
        }

        for(i = 0; i < n; ++i) {
            if(check(i, n)) {
                std::cout << i + 1 << std::endl;
                break;
            }
        }
    }
}


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

int main()
{
    int n;
    cin >> n;
    vector<int> a(60001);
    rep(i,100) {
        rep(j, 100) {
            rep(k, 100) {
                int b = (i * i) + (j * j) + (k * k) + (i * j) + (j * k) + (i * k);
                a[b]++;
            }
        }
    }
    rep(i,n) {
        cout << a[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 3596
using System;

public class Hello
{
    public static void Main()
    {
        while (true)
        {
            var n = int.Parse(Console.ReadLine().Trim());
            if (n == 0) break;
            var r = new int[7];
            for (int i = 0; i < n; i++)
            {
                var a = int.Parse(Console.ReadLine().Trim());
                var r0 = a / 10;
                if (r0 >= 6) r[6]++;
                else r[r0]++;
            }
            foreach (var x in r) Console.WriteLine(x);
        }
    }
}

Measured memory_bytes: 9200
use proconio::fastout;
use whiteread::parse_line;

#[fastout]
fn main() {
    let mut s: Vec<char> = parse_line::<String>().unwrap().chars().collect();
    s.sort();
    if s == vec!['a', 'b', 'c'] {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 2120
#include <bits/stdc++.h>
using lint=long long;
#define LOOP(x) for(long long ngtkana_is_a_genius=0;ngtkana_is_a_genius<x;ngtkana_is_a_genius++)

int main(){
    std::cin.tie(nullptr);std::cin.sync_with_stdio(false);
    int k,q;std::cin>>k>>q;
    std::vector<lint>a(k);
    for(int i=0;i<k;i++){
        std::cin>>a.at(i);
    }
    LOOP(q){
        int n,x,m;std::cin>>n>>x>>m;
        lint X=0;
        lint eq=0;
        for(int i=0;i<k;i++){
            X+=a.at(i)%m;
            if(a.at(i)%m==0)eq++;
        }
        X*=(n-1)/k;
        eq*=(n-1)/k;
        for(int i=0;i<(n-1)%k;i++){
            X+=a.at(i)%m;
            if(a.at(i)%m==0)eq++;
        }
        X+=x;
        std::cout<<n-1-X/m+x/m-eq<<std::endl;
    }
}

Measured memory_bytes: 512
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f3f3f3f3f;

LL ans = 0,mxd;
LL edg[55][55],dis[55][55];
LL n,a[55],b[55];

LL highbit(LL x){
	LL cnt = 0;
	while(x){ cnt ++; x >>= 1; }
	return cnt - 1;
}

void del(LL x){
	for(LL i = 0;i <= 50;i ++) edg[i][i % x] = 0;
}

void floyd(){
	memset(dis,INF,sizeof(dis));
	for(LL i = 0;i <= 50;i ++){
		for(LL j = 0;j <= 50;j ++){
			dis[i][j] = edg[i][j];
		}
	}
	for(LL k = 0;k <= 50;k ++){
		for(LL i = 0;i <= 50;i ++){
			for(LL j = 0;j <= 50;j ++){
				dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	memset(edg,INF,sizeof(edg));
	for(LL i = 0;i <= 50;i ++) edg[i][i] = 0;
	for(LL i = 0;i <= 50;i ++){
		for(LL j = 1;j <= 50;j ++){
			edg[i][i % j] = min(edg[i][i % j],(1LL << j));
		}
	}
	floyd();
	
	cin >> n;
	for(LL i = 1;i <= n;i ++) cin >> a[i];
	for(LL i = 1;i <= n;i ++) cin >> b[i];
	for(LL i = 1;i <= n;i ++) if(a[i] < b[i]){ cout << -1 << endl; return 0; }
	
	while(1){
		mxd = 0;
		for(LL i = 1;i <= n;i ++) mxd = max(mxd,dis[a[i]][b[i]]);
		if(!mxd) break;
		if(mxd == INF){ cout << -1 << endl; return 0; }
		
//		cout << mxd << ' ' << highbit(mxd) << endl;
		del(highbit(mxd)); floyd();
		ans += (1LL << highbit(mxd));
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main()
{
    int n = 0;
    cin >> n;
    int x = 0;
    int y = 0;
    for(x = 1;x<=9;x++)
    {
        for(y = 1;y<=9;y++)
        {
            if(x*y==n)
            {
                cout<<"Yes";
                n = -1;
                break;
            }
        }
    }
    if(n != -1)
    {
        cout<<"No";
    }
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    N, X, T = map(int, input().split())
    print((N+(X-1))//X*T)

if __name__ == "__main__":
    main()

Measured memory_bytes: 64860
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C =  list(map(int,input().split()))
point = 0
check = 0
for i in A:
  if check == i:
    point += C[i-2]
  point += B[i-1]
  check = i + 1
print(point)

Measured memory_bytes: 3064
# 4 5 (4 cities and 5 steps)
# 3 2 4 1

# 1 => 3
# 2 => 2
# 3 => 4
# 4 => 1

# 1 (0)
# 1 => 3 (1)
# 3 => 4 (2)
# 4 => 1 (3)

# 2 を作る 5 と2 と 1 を使う
# 2  = (5 - 3) % 2 + 3 - 1

N, K = map(int, input().split())
A_i = list(map(int, input().split()))

paths = {}

for i in range(N):
    paths[i+1] = A_i[i]

# print('paths:', paths)

# 6 5 2 5 3 2

# 1 => 6 (1)
# 6 => 2 (2)
# 2 => 5 (3)
# 5 => 3 (4)
# 3 => 2 (5)

# loop_steps = 5 - 2 - 1 = 2
# 5 + 2 * m + r = 727202214173249351
# steps + loop_steps * m + r = K
# r = (K - steps) % loop_steps

state = 1
steps = 0
flag = False
known_states = {}

while steps < K:
    known_states[state] = steps # state => 2, steps => 2

    state = paths[state] # state => 5
    steps += 1 # steps => 3

    # print(f'steps: {steps}, state: {state}')

    if state in known_states and not flag: # state => 2 steps => 5
        loop_steps = steps - known_states[state]
        K = (steps - loop_steps) + (K - (steps - loop_steps))  % loop_steps
        # print('loop_steps:', loop_steps)
        # print('steps - loop_steps:', steps - loop_steps)
        # print('K:', K)
        state = 1
        steps = 0
        # print('steps:', steps)
        flag = True
        # print('loop detected')



print(state)


Measured memory_bytes: 48700
import sys
sys.setrecursionlimit(4100000)
import math
INF = 10**9
import fractions

def main():
    X = list(map(int, input().split()))

    ans = 0
    for i in range(5):
        if X[i]==0:
            if i==4:
                ans = X[i-1]+1
                print(ans)
                return
            ans = X[i+1]-1
            print(ans)
            return



if __name__ == '__main__':
    main()


Measured memory_bytes: 72656
#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, m;
  cin >> n >> m;
  vector<P> ab(n);
  rep(i, n) {
    int a, b;
    cin >> a >> b;
    ab.at(i) = make_pair(a, b);
  }
  vector<P> cd(m);
  rep(i, m) {
    int c, d;
    cin >> c >> d;
    cd.at(i) = make_pair(c, d);
  }

  vector<int> res(n);
  rep(i, n) {
    int a = ab.at(i).first;
    int b = ab.at(i).second;
    int dis = INT_MAX;
    int minI = -1;
    rep(j, m) {
      int c = cd.at(j).first;
      int d = cd.at(j).second;
      int tmp = abs(a - c) + abs(b - d);
      if (tmp < dis) {
        dis = tmp;
        minI = j + 1;
      }
    }
    res.at(i) = minI;
  }
  rep(i, n) {
    cout << res.at(i) << endl;
  }
  return 0;
}


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

public class Main {
	public static void main(String[] args) throws Exception {
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		while(in.nextToken()!=in.TT_EOF) {
			int T=(int) in.nval;
			in.nextToken();
			int K=(int) in.nval;
			BigInteger[] b=new BigInteger[T];
			BigInteger[] b1=new BigInteger[T-K+1];
			int p=0,count=0;
			BigInteger b3=new BigInteger("1");
			for(int i=0;i<T;i++) {
				in.nextToken();
				b[i]=BigInteger.valueOf((long) in.nval);
				b3=b3.add(b[i]);
				p++;
				if(p==K) {
					b1[count++]=b3;
				}else if(p>K){
					b3=b3.subtract(b[i-K]);
					b1[count++]=b3;
				}
			}
			for(int i=0;i<b1.length-1;i++) {
				if(b1[i].compareTo(b1[i+1])<0) {
					System.out.println("Yes");
				}else {
					System.out.println("No");
				}
			}
		}
	}
}


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

int main()
{
    int A,B;
    cin >> A>>B;

    int i;

    for (int i = 1; i <=3; i++)
    {
    if(A!=i && B!=i){


        cout<<i<<endl;
    }
    
    }
}

Measured memory_bytes: 256
<?php
const INPUT_DELIMITER = " ";
const OUTPUT_DELIMITER = " ";

// 標準入力
$N = fgets(STDIN);
$input = fgets(STDIN);
$inputArray = explode(INPUT_DELIMITER, $input);

$nums = [];
foreach ($inputArray as $input) {
    $nums[] = (int)$input;
}
sort($nums);
//var_dump($nums);

$index = $N / 2;
$K = $nums[$index] - $nums[$index-1];
echo $K;

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

int n,a[20];

bool solve(int x,int y){
    if(y==0) return true;
    if(x>=n) return false;
    
    bool res = solve(x+1,y)||solve(x+1,y-a[x]);
    return res;
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    
    int b;
    scanf("%d",&b);
    for(int j=0;j<b;j++){
        int c;
        scanf("%d",&c);
        
        if(solve(0,c)) printf("yes\n");
        else printf("no\n");
    }
}


Measured memory_bytes: 3168