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

using namespace std;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
    ifstream t("/proc/self/status");
    cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getchar());
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) - '0' + ch;
	return sum * fg;
}

typedef long long LL;
typedef long double LD;
typedef unsigned int UI;
typedef pair<int, int> pii;

const int MAXN = (int) 2e3;

int n, m;

int A[MAXN + 5][MAXN + 5];

inline int safe_getchar()
{
	register char ch(getchar());
	while(ch != '#' && ch != '.') ch = getchar();
	return ch == '#';
}

inline void input()
{
	n = read<int>(), m = read<int>();
	for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j)
		A[i][j] = safe_getchar();
}

inline void solve()
{
	if(n == 1) { printf("%d\n", m); return; }
	if(m == 1) { printf("%d\n", n); return; }

	static int B[MAXN + 5][MAXN + 5];
	for(int i = 1; i < n; ++i) for(int j = 1; j < m; ++j)
		B[i][j] = (A[i][j] + A[i + 1][j] + A[i][j + 1] + A[i + 1][j + 1]) % 2 == 0;

	int ans = max(n, m);
	--n, --m;

	static int h[MAXN + 5][MAXN + 5];

	for(int j = 1; j <= m; ++j)
		for(int i = 1; i <= n; ++i)
			h[i][j] = B[i][j] == 0 ? 0 : h[i - 1][j] + 1;

	for(int i = 1; i <= n; ++i)
	{
		static int l[MAXN + 5], r[MAXN + 5];

		static vector<int> S;
		S.clear();

		for(int j = 1; j <= m; ++j)
		{
			while(!S.empty() && h[i][S.back()] >= h[i][j]) S.pop_back();
			l[j] = S.empty() ? 1 : S.back() + 1;
			S.push_back(j);
		}

		S.clear();
		for(int j = m; j; --j)
		{
			while(!S.empty() && h[i][S.back()] >= h[i][j]) S.pop_back();
			r[j] = S.empty() ? m : S.back() - 1;
			S.push_back(j);
		}

 		for(int j = 1; j <= m; ++j) chkmax(ans, (h[i][j] + 1) * (r[j] - l[j] + 1 + 1));
	}
	printf("%d\n", ans);
}

int main()
{

	input();
	solve();

	return 0;
}



Measured memory_bytes: 47360
#include <iostream>
#include <string>
#include <vector>

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main() {
  int a, b;
  cin >> a >> b;

  int sum = 0;
  for(int i=1; i <= 999; i++) {
    if (i == b - a) break;
    sum += i;
  }

  cout << sum - a << endl;

  return 0;
}


Measured memory_bytes: 256
class tree:
    def __init__(self,n):
        self.edge = [set() for i in range(n)]
    def add_edge_dual(self,f,e):
        self.edge[f].add(e)
        self.edge[e].add(f)
    def add_edge_single(self,f,e):
        self.edge[f].add(e)
    def connected(self,node):
        return self.edge(node)


def dfs(graph,s):
    visited = [False for i in range(len(graph.edge))]
    distance = [-1 for i in range(len(visited))]
    visited[s] = True
    distance[s] = 0
    buf = [[s]]
    now = s
    while len(buf) != 0:
        nexts = buf[0]
        buf = buf[1:]
        temp = []
        for nex in nexts:
            for child in graph.edge[nex]:
                if visited[child] == False:
                    distance[child] = distance[nex]+1
                    temp.append(child)
                    visited[child] = True
                else:
                    continue
        if len(temp) == 0:
            continue
        else:
            buf.append(temp)
    return  distance



n,u,v = map(int,input().split())
t = tree(n)

for i in range(n-1):
    a,b = map(int,input().split())
    t.add_edge_dual(a-1,b-1)

taka = dfs(t,u-1)
aoki = dfs(t,v-1)

aofar = -1
for i in range(n):
    if taka[i] < aoki[i]:
        if aoki[i] > aofar:
            aofar = aoki[i]


print(aofar-1)

# print(sorted(taka,key=lambda x:-x))
# print(sorted(aoki,key=lambda x:-x))
#
# print()
# print(far,aofar)

Measured memory_bytes: 41096
H, W, K = map(int, input().split())

def to_int(s):
    if s == ".":
        return 0
    else:
        return 1

c = [0] * H
for i in range(H):
    c[i] = list(map(to_int, input()))

res = 0
for h_bit in range(1<<H):
    for w_bit in range(1<<W):
        sum_c = 0
        h = h_bit
        for i in range(H):
            if h % 2 == 1:
                w = w_bit
                for j in range(W):
                    if w % 2 == 1:
                        sum_c += c[i][j]
                    w //= 2
            h //= 2
        if sum_c == K:
            res += 1
    
print(res)

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

int main()
{
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (auto& x : a) cin >> x;

    cout << (n - 1) / (k - 1) + !!((n - 1) % (k - 1)) << endl;

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9;
using namespace std;
using ll = long long;
int main() {
    int N , K;
    cin >> N >> K;
    vector <int> A(N);
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    int T = N - K;
    for(int i = 0; i < T; i++){
        if(A[i] < A[i + K]){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    }
}

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

#define REP(i,num) for(ll i=0;i<(num);++i)
#define FOR(i,c,num) for(ll (i)=(c);(i)<(num);++(i))
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=ll>
T in(){T x; cin >> x; return (x);}
template<typename T=ll,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return x;}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

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

	ll N=in();
	auto A=vecin(N);
	ll S = A[0];
	REP(i,N-1){
		S ^= A[i+1];
	}

	vector<ll> X(N);
	REP(i,N){
		X[i] = S^A[i];
	}
	PRINTALL(X);
	return 0;
}


Measured memory_bytes: 6300
#include<stdio.h>

int main(void){
    int N;
    scanf("%d",&N);
    int p;
    int count = 0;
    for(int i=0;i<N;i++){
        scanf("%d",&p);
        if(p!=i+1) count++;
    }
    if(count==0||count==2) printf("YES");
    else printf("NO");
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#define nmax_def 110000
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;

ll gcd(ll a, ll b)
{
	if (a == 0)
		return 0;
	if (b == 0)
		return 0;
	ll x;
	while (1)
	{
		x = a % b;
		if (x == 0)
			return b;
		else
		{
			a = b;
			b = x;
		}
	}
}

ll lcm(ll a, ll b)
{
	ll ans, gcd_ab;
	gcd_ab = gcd(a, b);
	ans = a * b / gcd_ab;
	return ans;
}

int main() {
	ll A, B;
	cin >> A >> B;
	ll ans = lcm(A, B);
	cout << ans << endl;


	return 0;
}

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

int main() {

  // int型の2次元配列(3×4要素の)の宣言
  vector<vector<int>> A(3, vector<int>(3));

  // 入力 (2重ループを用いる)
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      cin >> A.at(i).at(j);
    }
  }
  int N;
  cin >> N;
  vector<int> b(N);
  
for (int i = 0; i < N; i++) {
  cin >> b.at(i);
}
  
  int flag;
  flag=0;
  
 //ビンゴカードチェック 一致してたら0代入
  for (int k = 0; k < N; k++) {
     for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if (A.at(i).at(j)==b.at(k)){
        A.at(i).at(j)=0;
      }
    }
     }
  }
  
 //チェック後ビンゴカード表示
 //   for (int i = 0; i < 3; i++) {
 //    for (int j = 0; j < 3; j++) {
 //      cout << A.at(i).at(j)<<" ";
 //    }
 //     cout << endl;
 //  }

  //ビンゴ判定
    for (int i = 0; i < 3; i++) {
    if (A.at(0).at(i)+A.at(1).at(i)+A.at(2).at(i)==0){
      flag=1;
    }
     if (A.at(i).at(0)+A.at(i).at(1)+A.at(i).at(2)==0){
      flag=1;
     }

  }
       if (A.at(0).at(0)+A.at(1).at(1)+A.at(2).at(2)==0){
      flag=1; 
       }
       if (A.at(0).at(2)+A.at(1).at(1)+A.at(2).at(0)==0){
      flag=1;   
       }
  
  if (flag==1){cout<<"Yes"<<endl;} else {cout<<"No"<<endl;}
  
  
  
}

Measured memory_bytes: 256
def slove():
    import sys
    input = sys.stdin.readline
    a, b, c, d, e, f = list(map(int, input().rstrip('\n').split()))
    mn = 0
    x = y = 0
    for i in range(f // (a * 100) + 1):
        for j in range((f - 100 ** i) // (b * 100) + 1):
            for k in range((f - 100 * i - 100 * j) // c + 1):
                for l in range((f - 100 * i - 100 * j - k) // d + 1):
                    if 100 * i * a + 100 * j * b + c * k + d * l <= f:
                        if a * i + b * j != 0 and (c * k + d * l) / (a * i + b * j) <= e:
                            if mn < (c * k + d * l) / (100 * i * a + 100 * j * b + c * k + d * l):
                                if (100 * i * a + 100 * j * b + c * k + d * l) <= f:
                                    mn = (c * k + d * l) / (100 * i * a + 100 * j * b + c * k + d * l)
                                    x = 100 * i * a + 100 * j * b + c * k + d * l
                                    y = c * k + d * l
    if x == y == 0:
        print(a * 100, 0)
    else:
        print(x, y)



if __name__ == '__main__':
    slove()


Measured memory_bytes: 3064
#include<iostream>
#include<string>
using namespace std;
int main(void) {
	string S;
	string T;
	cin >> S;
	cin >> T;
	int Ans = 0;
	for (int i = 0; i < S.size(); i++) {
		if (S[i] != T[i]) {
			Ans += 1;
		}
	}
	cout << Ans << endl;
}

Measured memory_bytes: 3896
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
int main(){
  int n;
  while(cin >>n,n){
    vector<pair<double,double> > dot;
    bool f[100]={false};
    for(double i=0,a,b; i<n; i++){scanf("%lf,%lf",&a,&b);dot.push_back(make_pair(a,b));}
    sort(dot.begin(),dot.end());
    int now=0,next;
    for(;;){
      for(int i=0; i<n; i++){
	if(i!=now && !f[i]){
	  next = i;
	  double ax=dot[i].first-dot[now].first;
	  double ay=dot[i].second-dot[now].second;
	  for(int j=0; j<n; j++){
	    if(!f[j]){
	      double bx=dot[j].first-dot[now].first;
	      double by=dot[j].second-dot[now].second;
	      if(ax*by-ay*bx<0){next = -1;break;}
	    }
	  }
	  if(next == i) break;
	}
      }
      f[next] = true;
      now = next;
      if(f[0]) break;
    }
    int ans = 0;
    for(int i=0; i<n; i++) if(!f[i]) ans++;
    cout <<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 1280
if __name__ == '__main__':
    a,b= map(int,input().split())
    maxnum =0
    minnum =0
    diff = 10**9 +7
    ans = 0

    for i in range(b,a+2):
        max = (i * (2*a+1-i)) / 2
        min = (i* (i - 1) / 2)
        ans += max-min+1
        ans = ans % diff
    print(int(ans))


Measured memory_bytes: 9188
#include <iostream>
#include <string>

using namespace std;

bool const mask[][9] = {
    { true, true, true, false, false, false, false, false, false },
    { false, false, false, true, true, true, false, false, false },
    { false, false, false, false, false, false, true, true, true },
    { true, false, false, true, false, false, true, false, false },
    { false, true, false, false, true, false, false, true, false },
    { false, false, true, false, false, true, false, false, true },
    { true, false, false, false, true, false, false, false, true },
    { false, false, true, false, true, false, true, false, false }
};
bool j( string const& s, char const c )
{
    for( auto const& m : mask ) {
        bool matched = true;
        for( int i=0; i<9; ++i ) {
            if ( m[i] )
                matched &= s[i] == c;
        }
        if ( matched )
            return true;
    }

    return false;
}


int main()
{
    string s;
    while( cin >> s ) {
        cout << ( j( s, 'o')
                  ? 'o'
                  : j( s, 'x' )
                  ? 'x'
                  : 'd' )
             << endl;
    }
}

Measured memory_bytes: 1176
#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;
	cin >> n;
	int T, H;
	T = 0;
	H = 0;
	rep(i, n)
	{
		string a, b;
		cin >> a >> b;
		if (a > b)
			T += 3;
		else if (a == b)
		{
			T++;
			H++;
		}
		else
			H += 3;
	}
	cout << T << ' ' << H << endl;
}



Measured memory_bytes: 3160
#include<stdio.h>
using namespace std;
int main(){
    int a,b,c,count = 0;
    scanf("%d %d %d",&a,&b,&c);
    for(int i = a; i<=b; i++){
        if(c%i == 0) count++;
    }
    printf("%d\n",count);
    
}


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

int main() {
    int n;
    std::cin >> n;

    std::vector<int> A(n);
    for (int i = 0; i < n; i++) {
        std::cin >> A[i];
    }
    
    int q;
    std::cin >> q;
    for (int i = 0; i < q; i++) {
        int com, b, e;
        std::cin >> com >> b >> e;
        if (com == 0) {
            int min = *std::min_element(A.begin() + b, A.begin() + e);
            std::cout << min << std::endl;
        } else if (com == 1) {
            int max = *std::max_element(A.begin() + b, A.begin() + e);
            std::cout << max << std::endl;
        }
    }
}



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

#define int long long
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/2

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;

template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> void YesNo(T a) {cout<<(a?"Yes":"No")<<endl;}
template<class T> void YESNO(T a) {cout<<(a?"YES":"NO")<<endl;}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());}
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
    int n,W;
    cin>>n>>W;
    Vi w(n),v(n);
    REP(i,0,n) cin>>w[i]>>v[i];
    
    const int nmax=110,vmax=101000;
    VVi dp(nmax+1,Vi(vmax+1,INF));
    dp[0][0]=0;
    REP(i,0,n){
        REP(j,0,vmax){
            chmin(dp[i+1][j],dp[i][j]);
            if(j+v[i]<=vmax) chmin(dp[i+1][j+v[i]],dp[i][j]+w[i]);
        }
    }
    int ans=0;
    REP(i,0,vmax) if(dp[n][i]<=W) ans=i;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 88960
import scala.annotation.tailrec
import scala.io.StdIn

object Main extends App {

  val n = StdIn.readLine().toInt
  val buff = StdIn.readLine().split(' ').map(_.toInt)
  val out = Array.fill(n)(0)
  @tailrec def printReverse(index: Int): Unit = {
    if(index >= 0) {
      out(n - (index + 1)) = buff(index)
      printReverse(index - 1)
    }
  }
  
  printReverse(n-1)
  println(out.mkString(" "))
  
}


Measured memory_bytes: 44000
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;

#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}


fn main(){
    let line: Vec<u32> = read_as_vec();
    let (a, b) = (line[0], line[1]);

    if a <= 5{
        println!("0");
    }else if a <= 12{
        println!("{}", b/2);        
    }else{
        println!("{}", b);
    }
}


Measured memory_bytes: 4352
/*
 		Resilience is the greatest of all virtues.
 		Code by rajiv
 */
 #include <iostream>
 #include <cstring>
 #include <vector>
 #include <map>
 #include <set>
 #include <stack>
 #include <queue>
 #include <deque>
 #include <sstream>
 #include <iomanip>
 #include <cassert>
 #include <sys/time.h>
 #include <algorithm>
 #include <bitset>
 #include <cmath>
 #include <functional>
 #include <cmath>
 #include <climits>

 using namespace std ;

 #define xx first
 #define yy second
 #define ll long long
 #define ld long double
 #define el (char)0x0A
 #define sp " "
 #define pb push_back
 #define mp make_pair
 #define all(x) (x).begin(),(x).end()
 #define clr(x) memset((x),0,sizeof(x))
 #define uint unsigned int
 #define abs(x) ((x<=0)?(-x):(x))
 #define CASET  int t;cin>>t;while(t--)
 #define FORN(i,x,y) for(int i=x;i<y;i++)
 #define MAXN 100005
 #define INF 10000000010
 #define MOD 1000000007
 #define last_set_bit(x) log2((x)&(-x))
 #define add(x,y) (x)=((x)+(y))%MOD
 #define PI 3.141592653589793

 typedef pair<int,int> PII ; typedef vector<int> VI ; typedef vector<vector<int> > VVI ; typedef vector<bool> VB ; typedef vector<string> VS ;
 typedef map<int,int> MII ; typedef map<int,VI > MIV ; typedef set<int> SI ; typedef set<PII > SPII ; typedef vector<PII > VPII ; typedef vector<VPII > VVPII ;
 const int N = 100050 ;

string comp(string s1, string s2){
    if (s1.size() > s2.size()) return s1 ;
    else if (s1.size()<s2.size()) return s2 ;
    else {
        for(int i = 0 ; i < s1.size() ; i++){
            if (s1[i] > s2[i]) return s1 ;
            else if (s1[i] < s2[i]) return s2 ;
        }
        return s1 ;
    }

}

int main(){
     map<int, int> m ;
     m[1] = 2; m[2] = 5 ; m[3] = 5 ; m[4] = 4 ; m[5] = 5 ; m[6] = 6 ; m[7] = 3 ; m[8] = 7 ; m[9] = 6 ;
     ll N , M ; cin >> N >> M ;
     int a[M] ;
     for(int i = 0 ; i < M ; i++){
         cin >> a[i] ;
     }
     string L[N+1] ;
     L[0] = "";
     for(int i = 0 ; i <= N ; i++){
         L[i] = "" ;
     }

     for(int i = 0 ; i <= N ; i++){
         for(int j = 0 ; j < M ; j++){
             if (i != 0 && L[i] == "") continue ;
             if (i+m[a[j]] <= N){
                 L[i+m[a[j]]] = comp(L[i+m[a[j]]], L[i]+(char)('0'+a[j])) ;
                 // cout << i << sp << j << sp << i+m[a[j]] <<  sp << L[i+m[a[j]]] << el ;
            }
         }
     }
     cout << L[N] << el ;
}


Measured memory_bytes: 43136
# include <iostream>
# include <cmath>
# include <algorithm>
# include <stdio.h>
# include <cstdint>
# include <cstring>
# include <string>
# include <cstdlib>
# include <vector>
# include <bitset>
# include <map>
# include <queue>
# include <ctime>
# include <stack>
# include <set>
# include <list>
# include <random>
# include <chrono>
# include <deque>
# include <functional>
# include <iomanip>
# include <sstream>
# include <fstream>
# include <complex>
# include <numeric>
# include <cassert>
# include <array>
# include <tuple>
# include <cctype>
# include <unistd.h>
# include <unordered_map>
# include <unordered_set>
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define fast_work {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);}

const ll INF = 1e18 + 5, NMAX = 2e5 + 5, MOD = 998244353, N = 1e9 + 5, LOG = 25;
const ld EPS = 1e-8, pi = 3.14159265358979323846;

#define int long long

int x[NMAX];
int answer = 0;

set<pll> g[NMAX];

void solve() {
    int n;
    cin >> n;

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

    for(int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;

        g[u].insert({w + x[v], v});
        g[v].insert({w + x[u], u});
    }


    set< tuple<int, int, int> > operations;

    for(int i = 1; i <= n; ++i) {
        operations.insert({g[i].begin() -> f, g[i].begin() -> s, i});
    }

    while (!operations.empty()) {
        auto [w1, v1, i] = *operations.begin();
        operations.erase(operations.begin());

        if(w1 >= x[i]) continue;

        g[i].erase(g[i].begin());

        for(auto [w2, v2] : g[i]) {
            operations.erase({g[v1].begin() -> f, g[v1].begin() -> s, v1});
            operations.erase({g[v2].begin() -> f, g[v2].begin() -> s, v2});

            int w = w2 - x[v2];
            g[v2].erase({w + x[i], i});

            int new_w = w1 - x[v1] + w2 - x[v2];

            g[v2].insert({new_w + x[v1], v1});
            g[v1].insert({new_w + x[v2], v2});

            operations.insert({g[v1].begin() -> f, g[v1].begin() -> s, v1});
            operations.insert({g[v2].begin() -> f, g[v2].begin() -> s, v2});
        }

        g[i].clear();
        g[i].insert({w1, v1});
     }

    for(int i = 1; i <= n; ++i)
        for(auto [w, v] : g[i]) {
            //cout << i << " " << v << "\n";
            answer += (w + x[i]);
        }

    cout << answer / 2;
}

signed main() {
    fast_work

    int t = 1;
    //cin >> t;

    while (t --> 0) {
        solve();
    }
    
    return 0;
}

Measured memory_bytes: 64560
n,a,b=map(int,input().split())
h=[int(input())for _ in range(n)]
h.sort(reverse=True)
l=-1
r=10**9
while r-l>1:
	mid=(l+r)//2
	cnt=0
	for i in range(n):
		if h[i]-b*mid<=0:
			break
		else:
			cnt+=(h[i]-b*mid-1)//(a-b)+1
	if cnt>mid:
		l=mid
	else:
		r=mid
print(r)



Measured memory_bytes: 7440
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>
#include <complex>

const long INF = (1l << 30);
const long LINF = (1l << 60);

long n;

bool dig = true;
long p = 1;

long ans;

int main(){
    scanf("%ld", &n);
    for(long i = 1; i <= n; i++){
        if(i >= p*10){
            p *= 10;
            dig = !dig;
        }
        if(dig){
            ans++;
        }
    }
    printf("%ld\n", ans);
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>

using namespace std;
typedef long long ll;
using Graph = vector<vector<ll>>;

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

int main() {
    string S;
    cin >> S;
    cout << S.substr(0,3) << endl;
    return 0;
}


Measured memory_bytes: 3620
# ABC 110 , B
tmp = [int(el) for el in input().split(' ')]
n = tmp[0]
m = tmp[1]
x = tmp[2]
y = tmp[3]

X = [int(el) for el in input().split(' ')]
Y = [int(el) for el in input().split(' ')]

for z in range(x+1, y+1):
    if max(X) < z and min(Y) >= z:
        print('No War')
        break
else:
    print('War')


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


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

    double r;
    cin >> r;
    printf("%.10lf\n",2*M_PI*r);
    return 0;
}


Measured memory_bytes: 3740
use proconio::input;
use proconio::marker::{Chars, Usize1};
use std::iter::Iterator;
use std::collections::*;
use std::cmp::*;
use itertools::Itertools;

#[allow(unused_macros)]
macro_rules! max {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      max($x,max!($($xs)+))
    };
  }
  
  #[allow(unused_macros)]
  macro_rules! min {
    ($x:expr) => {
      $x
    };
    ($x:expr, $($xs:tt)+) => {
      min($x,min!($($xs)+))
    };
  }

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    input! {
    n: u64,
    k: u64,
    mut a: [u64; n],
    }

    // let mut res : u64 = 1;
    // for i in 0..k {
    //     res *= a[i as usize];
    // }

    // let mut res = 0;

    for i in k..n {
      //res = (res /  a[(i - k) as usize]) * a[i as usize];
      if a[i as usize] >  a[(i - k) as usize] {
        println!("Yes");
      }else {
        println!("No");
      }
    }


}


Measured memory_bytes: 5552
import java.lang.Long.max

fun main(args: Array<String>) {
    var (n, m, k) = readLine()!!.split(" ").map{it.toInt()}
    var a = readLine()!!.split(" ").map{it.toInt()}
    var b = readLine()!!.split(" ").map{it.toInt()}

    var a2 = mutableListOf(0L)
    var b2 = mutableListOf(0L)

    for(i in 0 until n) {
        a2.add(a[i] + a2[i])
    }
    for(i in 0 until m) {
        b2.add(b[i] + b2[i])
    }

    var ans = 0L
    var j = m
    for(i in 0..n) {
        if(a2[i] > k) break
        while(b2[j] > k - a2[i]) {
            j--
        }
        ans = max(ans, (i + j).toLong())
    }
    println(ans)
}

Measured memory_bytes: 89304
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 各冊数までの最大値を事前に用意しておく。
a, b=[0], [0]
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i]+B[i])

ans, j=0, M # ans=0, j=M
for i in range(N+1):
    if a[i]>K:
        break
    # Aがi冊の時、最大でBがj冊読める
    # Aが0冊(0分)、1冊(60分)、2冊(150分)の時、...
    # Bが4冊(460分)×、3冊(310分)×、2冊(230分)←Aが0冊なら○、...
    # => i:0 j:2(計2冊), i:1 j:1(計2冊), i:2 j:1(計3冊(最大)),
    #    i=3はKより大きくなりbreakとなる
    while b[j]>K-a[i]:
        j-=1
    # 今までのループでi+j冊の最大値を求める
    ans=max(ans, i + j)
print(ans)


Measured memory_bytes: 48764
import std.stdio, std.string, std.conv, std.range;
import std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, std.random, core.bitop;

enum inf = 1_001_001_001;
enum infl = 1_001_001_001_001_001_001L;
enum mod = 1_000_000_007L;


void main() {
    int N; long K;
    scan(N, K);
    auto a = readln.split.to!(long[]);

    long[] neg, pos;
    long zero;

    foreach (ai ; a) {
        if (ai < 0) neg ~= ai;
        else if (ai > 0) pos ~= ai;
        else zero++;
    }

    auto ns = neg.sort!"a > b"();
    auto ps = pos.sort();

    auto pn = ps.length.to!int;
    auto nn = ns.length.to!int;

    bool check(long x) {
        long cnt;

        if (x >= 0) {
            int r;
            foreach_reverse (i ; 0 .. pn) {
                while (r < pn && ps[i] * ps[r] <= x) {
                    r++;
                }
                cnt += r;
                if (i < r) cnt -= (r - i);
            }
            r = 0;
            foreach_reverse (i ; 0 .. nn) {
                while (r < nn && ns[i] * ns[r] <= x) {
                    r++;
                }
                cnt += r;
                if (i < r) cnt -= (r - i);
            }
            cnt += (zero - 1) * zero / 2 + zero * (N - zero);
            cnt += 1L * pn * nn;
        }
        else {
            int l = pn - 1;
            foreach (i ; 0 .. nn) {
                while (l >= 0 && ns[i] * ps[l] <= x) {
                    l--;
                }
                cnt += pn - 1 - l;
            }
        }

        debug {
            writefln("x: %s, cnt: %s", x, cnt);
        }

        return cnt >= K;
    }

    long ng = -infl, ok = infl;

    while (abs(ok - ng) > 1) {
        auto mid = (ok + ng) / 2;
        (check(mid) ? ok : ng) = mid;
    }

    writeln(ok);
}



void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}

void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

bool chmin(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x > arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}

bool chmax(T, U...)(ref T x, U args) {
    bool isChanged;

    foreach (arg; args) {
        if (x < arg) {
            x = arg;
            isChanged = true;
        }
    }

    return isChanged;
}


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

using namespace std;

int n,k;
const int mod = 1000000007;

int f[2][100001];

int main()
{
    cin >> n >> k; f[0][0] = 1; int a=0,b=0;
    for (int u,i=1; i<=n; i++)
    {
        b= (a+1)%2;
        cin >> u;
        int cur = 0;
        for (int i=0,j=0; i<=k; i++)
        {
            cur += f[a][i];
            if (cur < 0) cur += mod;
            else if (cur > mod) cur -= mod;
            f[b][i] = cur;

            if (j + u == i)
            {
                cur -= f[a][j];
                j++;
            }
        }
        a= b;
    }
    cout << f[a][k];
    return 0;
}


Measured memory_bytes: 1024
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <cmath>
#include <iomanip>

using namespace std;
using ll = long long;

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

#include <iostream>

int main()
{
	int P, Q, R;
	cin >> P >> Q >> R;

	cout << min(P+Q,min(Q+R,R+P)) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false); cin.tie(0);
#define endl '\n'
#define N 200000 + 5
#define ll long long int
using namespace std;

int n, a[N], b[N];

int main(){
    IOS;
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    for(int i=n; i>=1; i--){
        int sum = 0;
        for(int j=i+i; j<=n; j+=i){
            sum += b[j];
            sum %= 2;
        }
        b[i] = sum ^ a[i];
    }
    vector<int> ans; // index
    for(int i=1; i<=n; i++)
        if(b[i])
            ans.push_back(i);
    cout << ans.size() << endl;
    for(int i=0; i<ans.size(); i++)
        cout << ans[i] << " ";
    cout << endl;
    return 0;
}


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

#define forall(i, a, b) for (int i = a; i < b; i++)

// g++ -std=c++17 -O2 -Wall template.cpp -o template
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, d;
    cin >> n >> d;
    vector<int> x[n];
    forall(i, 0, n) {
        forall(j, 0, d) {
            int t;
            cin >> t;
            x[i].push_back(t);
        }
    }
    int count = 0;
    forall(i, 0, n) {
        forall(j, i + 1, n) {
            long double tot = 0;
            forall(k, 0, d) {
                tot += pow(x[i][k] - x[j][k], 2);
            }
            long double sq = sqrt(tot);
            if (ceil(sq) == floor(sq)) {
                count++;
            }
        }
    }
    cout << count << endl;
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // Solution
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Convert;
using static System.Math;

class Program
{
    static void Main(string[] args)
    {
        var num = ToInt32(ReadLine());
        var ar = new long[num];
        for (var i = 0; i < num; i++)
            ar[i] = ToInt32(ReadLine())%2;

        WriteLine(ar.Count(v => v == 1) == 0 ? "second" : "first");
    }
    private const string ALFA = "abcdefghijklmnopqrstuvwxyz";
    private const int MOD = 1000000007;
}


Measured memory_bytes: 15964
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int main(){
  int n,m,x,y;
  cin >> n >> m >> x >> y;
  vector<int> X(n);
  vector<int> Y(m);
  rep(i,0,n - 1) cin >> X[i];
  rep(i,0,m - 1) cin >> Y[i];
  for(int z = x + 1;z <= y;z++){
    bool OK = true;
    for(int xx : X){
      OK &= (xx < z);
    }
    for(int xx : Y){
      OK &= (xx >= z);
    }
    if(OK){
      cout << "No War" << endl;
      return 0;
    }
  }
  cout << "War" << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	long long int luc[86];
	int N;
	int i;
	luc[0] = 2;
	luc[1] = 1;

	scanf("%d", &N);
	for(i = 2; i < 87; i++) {
		luc[i] = luc[i-1] + luc[i-2];
	}
	printf("%lld", luc[N]);

	return 0;
}		

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n ;
  int result;
  result = 1;
  int k;
  cin >> k;
    for (int i = 0; i < n; i++)
    {
        if (result+k < result*2)
        {
            result = result + k;
        }
        else if (result*2 <= result+k)
        {
            result = result*2;
        }
        
        
    }
cout << result << endl;
  
  // ここにプログラムを追記

}

Measured memory_bytes: 3600
x,y = map(int,input().split())

def check(n):
    if n == 2:
        return 1
    elif n == 4 or n == 6 or n == 9 or n == 11:
        return 2
    else:
        return 3

if check(x) == check(y):
    print('Yes')
else:
    print('No')

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

int main() {
  string S; cin >> S;
  ll K; cin >> K;
  int n = -1;
  for (int i = 0; i < S.length(); ++i) {
    if (S[i] != '1') break;
    n = i;
  }
  if (n == -1) {
    cout << S[0] << endl;
  } else {
    cout << ( (K <= n + 1) ? S[0] : S[n + 1] ) << endl;
  }
  return 0;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  
  for(int i = 0; i < n; i++){
    cin >> a.at(i);
  }
  
    for(int i = 0; i < n; i++){
      if(a.at(i)%2==1){
        if(i==n-1){
          cout << "APPROVED" << endl;
        }
      }
      else if(a.at(i)%2==0){
      if(a.at(i)%3==0 || a.at(i)%5==0){
        if(i==n-1){
          cout << "APPROVED" << endl;
        }
      }
      else{
        cout << "DENIED" << endl;
        break;
      }
    }
  }    
}

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

int main() 
{
	int n, k;
	scanf("%d%d", &n, &k);
	bool dp[k+1]; 
	int a[n];
	for(int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	memset(dp, 0, sizeof(dp));
	for(int i = 0; i < k + 1; i++) {
		for(auto it : a) {
			if(i - it >= 0 && !dp[i]) {
				dp[i] = dp[i-it]^1;
			}
		}
	}
	if(dp[k]) puts("First");
	else puts("Second");
}

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

int main() {
	int N;
  	cin >> N;
  	vector<int> m(N);
  	int flag=0;
  for(int i=0;i<N;i++){
    cin >> m.at(i);
  }
  for(int i=0;i<N;i++){
    	if(m.at(i)%2==0){
         if(m.at(i)%3==0 || m.at(i)%5==0);
         else flag=1;
        }
  }
  if(flag==0)cout<<"APPROVED"<<endl;
  else cout<<"DENIED"<<endl;
}


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

const ll MOD = 998244353;

struct Combination
{
    int maxn;
    vector<ll> fmemo;
    vector<ll> imemo;
    vector<ll> ifmemo;
    
    ll modpow(ll x, ll n){
        ll res = 1;
        ll mul = x;
        while(n){
            if(n % 2) res = res * mul % MOD;
            mul = mul * mul % MOD;
            n /= 2;
        }
        return res;
    }

    Combination(int maxn) : maxn(maxn){
        fmemo.resize(maxn + 1);
        imemo.resize(maxn + 1);
        ifmemo.resize(maxn + 1);
        for(ll i = 1; i <= maxn; i++){
            imemo[i] = modpow(i, MOD - 2);
        }
    }

    ll fact(ll n){
        if(n == 0) return 1;
        if(fmemo[n]) return fmemo[n];
        return fmemo[n] = n * fact(n - 1) % MOD;
    }

    ll ifact(ll n){
        if(n == 0) return 1;
        if(ifmemo[n]) return ifmemo[n];
        return ifmemo[n] = imemo[n] * ifact(n - 1) % MOD;
    }

    ll com(ll n, ll k){
        if(k > n) return 0;
        if(k == n || k == 0) return 1;
        return (fact(n) * ifact(k) % MOD) * ifact(n - k) % MOD;
    }
};

int main()
{
    int n, m;
    cin >> n >> m;
    Combination c(m * 3 + n + 1);
    ll ans = c.com(n + m * 3 - 1, n - 1);
    ans = (ans + MOD - c.com(n + m - 2, n - 1) * n % MOD) % MOD;
    for(int i = m + 1; i <= max(n, m * 3); i++){
        if((m * 3 - i) % 2) continue;
        ans = (ans + MOD * 2 - c.com(n, i) * c.com(n + (m * 3 - i) / 2 - 1, n - 1) % MOD) % MOD;
    }
    cout << ans << endl;
}

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

int main(){
    int n, m; cin >> n >> m;
    vector<vector<int> > G(n);
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(int i = 0; i < n; i++){
        cout << G[i].size() << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
long long a[N],ans;
int n,k;
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1);
	reverse(a+1,a+n+1);
	for(int i=k+1;i<=n;i++)
		ans+=a[i];
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

class Solution {
private:
    int N;
    unordered_set<string> str_set;
public:
    void load() {
        cin >> N;
        string s;
        for (int i = 0; i < N; ++i) {
            cin >> s;
            str_set.insert(s);
        }
    }

    size_t solve() {
        return str_set.size();
    }
};

int main() {
    Solution sol;
    sol.load();
    cout << sol.solve() << endl;
}

Measured memory_bytes: 13828
#include<stdio.h>
/*複数のデータセットに対して、各々が直角三角形か
どうか判定する*/
void right_triangle(int x, int y, int z);

int main(void)
{
    int n;//nはデータセットの個数
    scanf("%d", &n);
    for ( int i = 0; i <n ; ++i){
    int a, b, c;//a,b,cは辺の長さ
    scanf("%d %d %d", &a, &b, &c);
    right_triangle(a , b, c);
    }
    return 0;
}    

void right_triangle( int x, int y, int z)
{
    x *= x;
    y *= y;
    z *= z;
    if (x == y + z|| y == z + x|| z == x + y){
        printf("YES\n");
    }else{
        printf("NO\n");
    }
}

Measured memory_bytes: 1008
n=int(input())

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n //= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table
print("{0:d}".format(n)+": "+" ".join(map(str,prime_decomposition(n))))

Measured memory_bytes: 7780
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;



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

	long long x, y, xx, yy, i, j, k, ans, MOD = 998244353;
	cin >> x >> y >> xx >> yy;
	vector<vector<long long>> dp(xx + 1, vector<long long>(yy + 1, 0));
	for (i = 1; i <= xx; i++) {
		if (i < x) continue;
		for (j = 1; j <= yy; j++) {
			if (j < y) continue;
			if ((i == x) && (j == y)) dp[i][j] = 1;
			else {
				dp[i][j] = (dp[i - 1][j] * j + dp[i][j - 1] * i) % MOD;
				dp[i][j] = (dp[i][j] + MOD * MOD - dp[i - 1][j - 1] * (j - 1) * (i - 1)) % MOD;

				//dp[i][j] = (dp[i - 1][j] * dp[i][j - 1]) % MOD;
				//dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * (i + j - 2)) % MOD;


//				dp[i][j] = (dp[i][j] + MOD * MOD - dp[i - 1][j] * dp[i][j - 1]) % MOD;

				//dp[i][j] = (dp[i][j] + MOD * MOD - dp[i - 1][j] * dp[i][j - 1]) % MOD;
			}
		}
	}
	ans = dp[xx][yy] % MOD;
	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 73388
from collections import Counter,deque
def bfs(G,s,N):
    dist=[-1]*(N+1)
    d=deque()
    dist[s]=0
    d.append(s)
    while(len(d)!=0):
        v=d[0]
        d.popleft()
        for nv in G[v]:
            if(dist[nv]!=-1):
                continue
            #発見した地点への操作
            dist[nv]=dist[v]+1
            d.append(nv)
            #ここまで
    return dist

N,X,Y=map(int,input().split())
G=[[] for i in range(N+1)]
for i in range(1,N):
    G[i].append(i+1)
    G[i+1].append(i)
G[X].append(Y);G[Y].append(X)
Count=[0]*(N+1)
for i in range(1,N+1):
    li=bfs(G,i,N)
    c=Counter(li)
    for i in range(1,N+1):
        Count[i]+=c[i]
for i in range(1,N):
    print(Count[i]//2)

Measured memory_bytes: 71772
#include <iostream>
using namespace std;
int main(){
  int N, M;
  cin >> N >> M;
  int a[M], b[M];
  for(int i = 1; i <= M; ++i){
    cin >> a[i] >> b[i];
  }
  for(int k = 1; k <= N; ++k){
      int sum = 0;
      for(int i = 1; i <= M; ++i){
          if(a[i] == k || b[i] == k){
            sum = sum + 1;
          }
        }
          cout << sum << endl;
  }
}


Measured memory_bytes: 256
///Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;
#define                          ll                          long long int
ll gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}

#define                          in(x)                       scanf("%lld",&x)
#define                          in2(x,y)                    scanf("%lld %lld",&x,&y)
#define                          in3(x,y,z)                  scanf("%lld %lld %lld",&x,&y,&z)
#define                          out(x)                      printf("%lld\n",x)
#define                          cy                          printf("YES\n")
#define                          cn                          printf("NO\n")
#define                          inf                         1e18
#define                          neg                         -1e18
#define                          mx                          2111111
#define                          fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define                          fi                          first
#define                          si                          second
#define                          ce                          cout<<endl
#define                          pb                          push_back
#define                          vc(x)                       x.begin(),x.end()
#define                          pb                          push_back
#define                          pi                          pair<ll,ll>
#define                          debug                       printf("ok\n");
#define                          pg                          pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> >
#define                          mod                         1000000007
#define max4(a,b,c,d)           max(a,max(b,max(c,d)))

int main()
{

    ll i,j,t,cas=0,k;
    ll a,b,c,d;
    in2(a,b);
    in2(c,d);
    if(a>=0 and b>=0 and c>=0 and d>=0)
      cout<<max(a,b)*max(c,d)<<endl;
    else
    {
        ll okmx1=max(a,b);
        ll okmn1=min(a,b);
        ll okmx2=max(c,d);
        ll okmn2=min(c,d);
        ll okans=max4(okmn1*okmn2,okmx1*okmx2,okmx1*okmn2,okmx2*okmn1);
        out(okans);
    }

}



Measured memory_bytes: 3824
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const ll mod = 1000000007;
const int INF = 1001001001;
const ll LINF = 1001001001001001001;

int main(){
    ll n,k; cin >> n >> k;
    ll ans = 0;
    if(k==0){
      	cout << n * n << endl;
      	return 0;
    }
    for(int b=k+1;b<=n;b++){
        ll md = n%b;
        if(md<k){
            ans += (n/b)*(b-k);
        }else{
            ans += (n/b)*(b-k) + (md-k+1);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int r = sc.nextInt();
        if(r<1200){
            System.out.println("ABC");
        }else if(r>=1200 && r<2800){
            System.out.println("ARC");
        }else{
            System.out.println("AGC");
        }
    }

}


Measured memory_bytes: 20820
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using p = pair<int,int>;
const long long INF = 1ll << 60;



int main() {
  int x;
  cin >> x;
  if(x == 0) cout << 1 << endl;
  else cout << 0 << endl;
	return 0;
}



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

int main()
{
    string s;
    cin >> s;
    map<char, int> mp;
    for (int i = 0; i < 4; i++)
    {
        mp[s[i]] += 1;
    }
    if (mp.size() != 2)
    {
        cout << "No" << endl;
        return 0;
    }

    for (auto i = mp.begin(); i != mp.end(); i++)
    {
        // cout << i->first << " " << i->second << "\n";
        if (i->second != 2)
        {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int q = scanner.nextInt();
        for (int n = 0; n < q; n++) {
            String x = scanner.next();
            String y = scanner.next();
            int[][] c = new int[x.length() + 1][y.length() + 1];
            for (int i = 1; i < x.length() + 1; i++) {
                for (int j = 1; j < y.length() + 1; j++) {
                    if (x.charAt(i - 1) == y.charAt(j - 1)) {
                        c[i][j] = c[i - 1][j - 1] + 1;
                    } else {
                        c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);
                    }
                }
            }
            System.out.println(c[x.length()][y.length()]);
        }
    }
}

Measured memory_bytes: 64444