akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2
void DFS();
void DFS_visit(int );

int color[N],d[N],f[N],time;
int n,M[100][100]; //0オリジン

int main()
{
  int u,k,v;
  int i,j;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      M[i][j]=0;  //M[0][0]=0,M[1][1]=0, ...
    }
  }
  for(i=0;i<n;i++){
    scanf("%d%d",&u,&k);
    u=u-1; //0オリジンへ変換
    for(j=0;j<k;j++){
      scanf("%d",&v);
      v=v-1; //0オリジンへ変換
      M[u][v] = 1; // 辺作成
    }
  }

  DFS(); //深さ優先探索

  return 0;
}

void DFS(){
  int u,i;
  /* 初期化 */
  for(i=0;i<n;i++) color[i] = WHITE;
  time=0;
  
  for(u=0;u<n;u++){
    if(color[u] == WHITE) DFS_visit(u); //WHITE=未訪問であるから、訪問する。
  }
  for(i=0;i<n;i++){
    printf("%d %d %d\n",i+1,d[i],f[i]); //頂点の番号、発見時刻、完了時刻の出力
  }
}

void DFS_visit(int u){
  int v;
  
  color[u] = GRAY; //一回訪問すると、GRAYになる。
  time++;
  d[u] = time; //発見
  for(v=0;v<n;v++){
    if(M[u][v]==0) continue;
    if(color[v]==WHITE) DFS_visit(v); //まだ一度も訪問していなかったら、再帰する。
  }
  color[u] = BLACK; //二度目の訪問で、BLACKになる。
  time++;
  f[u] = time; //完了
}

  


   
     



Measured memory_bytes: 2048
//“First, solve the problem. Then, write the code.” – John Johnson
/* Author: Mihir Arora*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long int power(long long int x, unsigned long long int y) 
{ 
    if (y == 0) 
        return 1; 
    else if (y % 2 == 0) 
        return power(x, y / 2) * power(x, y / 2); 
    else
        return x * power(x, y / 2) * power(x, y / 2); 
} 
inline void solve()
{
      //lets begin; 
     int n; 
     cin>>n; 
      int mapp1=0,mapp2=0,mapp3=0,mapp4=0; 
     for(int i=0;i<n;i++)
     {
        string s; 
        cin>>s; 
        if(s=="AC")
        mapp1++; 
        else if(s=="WA")
        mapp2++; 
        else if(s=="TLE")
        mapp3++; 
        else
        mapp4++; 
     }
     cout<<"AC x "<<mapp1<<"\n"; 
      cout<<"WA x "<<mapp2<<"\n"; 
       cout<<"TLE x "<<mapp3<<"\n";
   
        cout<<"RE x "<<mapp4; 
    //check one last time before submitting(-50); 
}
int main()
{
// 	int t; 
//     cin>>t; 
//     while(t--)
//     {
        solve(); 
    //     cout<<"\n"; 
    // }
}

Measured memory_bytes: 3624
#include <iostream>

using namespace std;

int main()
{

    int x,i,j;
    string s;
    cin>>x>>s;
    for(i=0; i<s.length(); i++){
        if(s[i]-'A'+x<26)
        s[i]=s[i]+x;
        else
            s[i]=abs(26-s[i]-x);
    }

                                cout<<s;
    return 0;
}


Measured memory_bytes: 256
#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++)
 
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
 
const long long INF = 1LL << 60;
#define PI 3.14159265359 
bool dp[100100];

template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}

int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}

long long lcm (int a, int b){
    return  (long long) a*b /gcd(a,b);
}



int main(){
    string S;
    int N;
    cin >> N >> S;

    rep(i,S.size()){
        char c = S[i] + N;
        if (c > 'Z'){
            c -= 26;
        }
        cout << (char) c ; 
    }
    cout << endl;






}


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

int main() {
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif

    int a,b;
    cin>>a>>b;
    int sockets = 1, strips = 0;
    while(sockets < b) {
        sockets += a-1;
        strips++;
    }
    cout<<strips<<endl;
}

Measured memory_bytes: 256
N = int(input())
S = [input() for _ in range(N)]

last_A = []
first_B = []
A_B = []
for i in range(N):
    if (S[i][0] == 'B' and S[i][-1] == 'A'):
        A_B.append(S[i])
    elif (S[i][0] == 'B'):
        first_B.append(S[i])
    elif (S[i][-1] == 'A'):
        last_A.append(S[i])

count = 0
for i in S:
    for j in range(len(i) - 1):
        if i[j] == 'A' and i[j + 1] == 'B':
            count += 1


def calc_comb(sb, fa, sbfa):
    if sbfa == 0:
        return min(sb, fa)
    elif sb == 0 and fa == 0:
        return sbfa - 1
    else:
        return sbfa + min(sb, fa)


print(count + calc_comb(len(first_B), len(last_A), len(A_B)))


Measured memory_bytes: 9756
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define fi first
#define se second
const int MAX = 200000; //2 * 10^5
const int MOD = 1000000007; //10^9 + 7
const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;

int32_t main()
{
	int n, m, s = 0;
	cin >> n >> m;
	vector<int> arr(n + 1);
	for(int i = 1; i <= n; i++)
		cin >> arr[i], s += arr[i];

	int cnt = 0;
	
	for(int i = 1; i <= n; i++)
		if(s <= 4 * m * arr[i])
			cnt++;

	if(cnt >= m) puts("Yes");
	else puts("No");
	
	return 0;
}

Measured memory_bytes: 256
import fractions


def run(n, x, xx):
    xx.append(x)
    xx = sorted(xx)
    d = [xx[i+1]-xx[i] for i in range(n)]
    d = sorted(d)
    min_d = d[0]
    if len(d) == 1:
        pass
    else:
        for i in range(1, len(d)):
            min_d = fractions.gcd(min_d, d[i])
    return min_d


def main():
    n, x = map(int, input().split())
    xx = list(map(int, input().split()))
    print(run(n, x, xx))


if __name__ == '__main__':
    main()


Measured memory_bytes: 16276
N = int(input())
S = input()
MOD = 10**9+7

alp = 'abcdefghijklmnopqrstuvwxyz'
count_alp = [0 for i in range(26)]
count = 1

for s in S:
    count_alp[alp.find(s)]+=1

for i in count_alp:
    count*= (i+1)
print((count-1)%MOD)

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

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

using namespace std;

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

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

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

void solve() {
  vi32 v(5);
  cin >> v;
  rep(i, 5) {
    if (v[i] == 0) {
      cout << i + 1 << endl;
    }
  }
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n, a, b;
    cin >> n >> a >> b;
    long long c;
    c = a+b;
    long long ans;
    ans = a*(n/c);
    ans += min(n%c,a);
    cout << ans << endl;
}

Measured memory_bytes: 256
// 17:05 -
#include <algorithm>
#include <iostream>

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

struct Job {
  int a, b;
};

bool comp(const Job &j1, const Job &j2) { return j1.b < j2.b; }

int main() {
  int n;
  std::cin >> n;
  Job jobs[n];

  rep(i, n) { std::cin >> jobs[i].a >> jobs[i].b; }

  std::sort(jobs, jobs + n, comp);

  int sum = 0;
  rep(i, n) {
    sum += jobs[i].a;
    // std::cout << sum << '\n';
    if (sum > jobs[i].b) {
      std::cout << "No" << '\n';
      return 0;
    }
  }

  std::cout << "Yes" << '\n';
  return 0;
}


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

int main()
{
	vector<bool> is_not_prime(50001);
	is_not_prime[1] = true;
	for (int i = 2; i <= 50000; ++i)
	{
		if (!is_not_prime[i])
		{
			for (int j = 2 * i; j <= 50000; j += i)
			{
				is_not_prime[j] = true;
			}
		}
	}

	while (true)
	{
		int n;
		cin >> n;
		if (n == 0)
		{
			return 0;
		}
		int count = 0;
		for (int i = 2; i <= n / 2; ++i)
		{
			if (!is_not_prime[i] && !is_not_prime[n - i])
				++count;
		}
		cout << count << endl;
	}
}

Measured memory_bytes: 3024
#include<iostream>
#include<vector>
#include<string>
#include<utility>
#include<algorithm>
#include<unordered_map>
using namespace std;

bool check_month(int num){
  if (1 <= num && num <= 12 ) return true;
  else return false;
}


int main()
{
    string s; cin >> s;
    int left = stoi( s.substr (0,2) );
    int right = stoi( s.substr (2,2) );

    bool left_month = check_month(left);
    bool right_month = check_month(right);

    if( left_month && right_month ){
      cout << "AMBIGUOUS" << endl;
    }
    else if( left_month && right_month == false ){
      cout << "MMYY" << endl;
    }
    else if( left_month == false && right_month ){
      cout << "YYMM" << endl;
    }
    else{
      cout << "NA" << endl;
    }
    return 0;
}


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

int main() {

  string a;
  cin >> a;
  
  cout << a[0] << a.size()-2 << a[a.size()-1] << endl;
  
}


Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

int N, M;
int P[100010];
set<int> G[100010];

int main (int argc, char const *argv[]) {
  cin >> N >> M;
  for (int i=0; i<N; ++i) cin >> P[i+1];

  for (int i=0; i<M; ++i) {
    int x,y;
    cin >> x >> y;
    G[x].insert(y);
    G[y].insert(x);
  }

  set<int> visit;

  size_t ans = 0;

  for (int i = 1; i <= N; i++) {
    if(visit.count(i)) continue;
    stack<int> q;
    set<int> iset,pset;
    q.push(i);
    iset.insert(i);
    pset.insert(P[i]);
    while(q.size()) {
      int f = q.top();q.pop();
      for(auto &&next:G[f]) {
        if(!visit.count(next)) {
          q.push(next);
          visit.insert(next);
          iset.insert(next);
          pset.insert(P[next]);
        }
      }
    }

    vector<int> intersection;
    set_intersection(iset.begin(),iset.end(),pset.begin(),pset.end(),back_inserter(intersection));
    ans += intersection.size();
  }


  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 29436
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
typedef long long int ll;

int main()
{
	string str;
	cin>>str;
	if(str == "ABC"){
		cout<<"ARC"<<endl;
	}else{
		cout<<"ABC"<<endl;
	}
	return 0;
}



Measured memory_bytes: 3620
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int N=1e5+10;
int n,m;
char s[100];
int main()
{
	int i,j,k;
	scanf("%s",s);
	n=strlen(s);
	for (i=0;i<n;i++)
	  if (s[i]=='9')
	  {
	  	printf("Yes");
	  	return 0;
	  }
	printf("No");
	return 0;
}

Measured memory_bytes: 128
from itertools import permutations

n,m=map(int,input().split())
path=set()
for _ in range(m):
    u,v=map(int,input().split())
    path|={(u-1,v-1),(v-1,u-1)}
s = 0
for i in permutations(range(n)):
    if i[0] ==0:

        s+=(all((h,j) in path for h,j in zip(i[1:],i)))


print(s)

Measured memory_bytes: 3064
import math
 
n=int(input())
t=int(input())
mint=t
t1=int(input())
if t1<t: mint=t1
maxtt=t1-t
 
 
for i in range(2,n):
    t=int(input())
  
    if t-mint>maxtt: maxtt=t-mint
    if t<mint: mint=t
     
print(int(maxtt))   


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

public class Main {
    private static boolean debug = false;
    private static boolean elapsed = false;

    private static PrintWriter _out = new PrintWriter(System.out);
    private static PrintWriter _err = new PrintWriter(System.err);

    private void solve(Scanner sc) {
        int N = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; ++i) {
            A[i] = sc.nextInt();
        }

        Arrays.sort(A);

        int t = 0;
        long sum = 0;
        for (int i = 0; i < N - 1; ++i) {
            if (2 * (sum + A[i]) < A[i + 1]) {
                t = i + 1;
            }
            sum += A[i];
        }
        _out.println((N - t));
    }
    private static BigInteger C(long n, long r) {
        BigInteger res = BigInteger.ONE;
        for (long i = n; i > n - r; --i) {
            res = res.multiply(BigInteger.valueOf(i));
        }
        for (long i = r; i > 1; --i) {
            res = res.divide(BigInteger.valueOf(i));
        }
        return res;
    }
    private static BigInteger P(long n, long r) {
        BigInteger res = BigInteger.ONE;
        for (long i = n; i > n - r; --i) {
            res = res.multiply(BigInteger.valueOf(i));
        }
        return res;
    }
    /*
     * 10^10 > Integer.MAX_VALUE = 2147483647 > 10^9
     * 10^19 > Long.MAX_VALUE = 9223372036854775807L > 10^18
     */
    public static void main(String[] args) {
        long S = System.currentTimeMillis();

        Scanner sc = new Scanner(System.in);
        new Main().solve(sc);
        _out.flush();

        long G = System.currentTimeMillis();
        if (elapsed) {
            _err.println((G - S) + "ms");
        }
        _err.flush();
    }
}

Measured memory_bytes: 50908
#include <bits/stdc++.h>
#define FOR(i, n) for(int i = 0;i <n;i++)
#define RFOR(i, n) for(int i = n;i >= 0;i--)
#define REP(i, m, n) for(int i = m;i < n;i++)
#define RREP(i, m, n) for(int i = m;i >= n;i--)
#define INF 999999999

using namespace std;
int main(int argc, char const *argv[])
{
 int a,b,i=0,n=0;
 cin >>a>>b;
 a = b - a;
 while(i != a)
 {
   i++;
   n +=i;
 }
 n -= b;
 cout<<n<<endl;

return 0;

}


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

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> h(n);
  rep(i,n) cin >> h.at(i);
  vector<vector<int>> road(n, vector<int>(0));
  rep(i,m) {
    int a, b;
    cin >> a >> b;
    road.at(a - 1).push_back(b);
    road.at(b - 1).push_back(a);
  }
  int cnt = 0;
  rep(i,n) {
    int good = 1;
    rep(j,road.at(i).size()) {
      if (h.at(i) <= h.at(road.at(i).at(j) - 1)) {
        good = 0;
        break;
      }
    }
    if (good == 1) {
      cnt++;
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 8728
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String S = scanner.next();
        scanner.close();

        int ans = 0;
        int tmp = 0;
        for (int i = 0; i < S.length(); ++i) {
            char s = S.charAt(i);
            if (s == 'A' || s == 'G' || s == 'T' || s == 'C') {
                ans = Math.max(ans, ++tmp);
            } else {
                tmp = 0;
            }
        }

        System.out.println(ans);
    }
}

Measured memory_bytes: 23892
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{

	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);

// #ifndef ONLINE_JUDGE
// 	freopen("input.txt" , "r" , stdin);
// 	freopen("output.txt" , "w" , stdout);
// #endif

	string s;
	cin >> s;
	ll c = 0, c1 = 0;
	ll l = s.length();
	ll i = 0;
	while (i < l - 2)
	{
		if (s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C')
		{
			c1 += c + 1;
			s[i] = 'B';
			s[i + 1] = 'C';
			s[i + 2] = 'A';
			if (c > 0)
				i = i + 2;
		}
		else if (s[i] == 'A')
		{
			c++;
			i++;
		}
		else
		{
			c = 0;
			i++;
		}
	}
	cout << c1 << endl;



}


Measured memory_bytes: 720
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    ll n, ans = 0;
    cin >> n;
    vector<ll> ret;
    for(ll i = 1; i*i <= n; i++){
        if(n % i == 0){
            ret.push_back(i);
            if(n != i*i)ret.push_back(n/i);
        }
    }
    n--;
    for(ll i = 1; i*i <= n; i++){
        if(n % i == 0){
            ret.push_back(i);
            if(n != i*i)ret.push_back(n/i);
        }
    }
    sort(all(ret));
    ret.erase(unique(all(ret)), ret.end());
    rep(i, ret.size()){
        if(ret[i] == 1)continue;
        ll a = n+1;
        while(a % ret[i] == 0)a /= ret[i];
        if(a % ret[i] == 1)ans++;
    }
    cout << ans << endl;
}   

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

int main(){
	int R, G, B, N;
	cin >> R >> G >> B >> N;
	ll ans = 0;
	int r_max = (N+R-1)/R;
	int g_max = (N+G-1)/G;
	rep(i,r_max+1)rep(j,g_max+1){
		int k = (N - i*R - j*G)/B;
		if (k < 0 ) break;
		if (i*R + j*G + k*B == N) ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3584
l = [int(input()) for i in range(4)]
a = 0
for i in range(l[2]+1):
    for j in range(l[1]+1):
        for k in range(l[0]+1):
            b = 50 * i + 100 * j 
            b += 500 * k 
            if b == l[3] :
                a += 1
                 
print('{}'.format(a))


Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
#include <iterator> 
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include<deque>
#include <regex>
#include <list>
#include <unordered_set>
#define rep(i,n) for(ll i=0;i<(n); ++i)
#define per(i,n) for(ll i=n-1;i>=0; --i)
#define all(x) (x).begin(),(x).end()
#define _GLIBCXX_DEBUG
using namespace std;
template<class T> inline bool dpmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool dpmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
typedef long long ll;
const ll MOD = 1000000007;
ll getDigit(ll n) {
	ll cnt = 0;
	while (n != 0) {
		n /= 10;
		cnt++;
	}
	return cnt;
}
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
typedef pair<double, long long> pair_t;
bool comp(const pair_t& a, const pair_t& b) {
	if (a.first == b.first)return  a.second > b.second;
	else {
		return a.first > b.first;
	}
}

int main() {
	vector<ll>dp(pow(10, 7));
	ll n;
	cin >> n;
	vector<ll>h(n);
	rep(i, n)cin >> h[i];
	rep(i, n)dp[i] = INF;

	dp[0] = 0;
	dp[1] = abs(h[1] - h[0]);
	for (ll i = 2; i < n; i++) {
		dpmin(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
		dpmin(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
	}
	cout << dp[n-1] << endl;
}


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

#define fi first
#define se second

const int N = 1000200;
const int MOD = 1e9 + 7;

using namespace std;

#define ll long long
ll dp[N];
ll pre[N];

int main()
{
        ios_base::sync_with_stdio(0);

        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);

        ll n;
	cin >> n;

	dp[0] = 1;
	pre[0] = 1;
	for(int i = 1; i < n; i++){
		dp[i] = pre[i - 1] + 1;

		if(i > 1){
			dp[i] -= dp[i - 2];
			if(dp[i] < 0){
				dp[i] += MOD;
			}
		} else if(i == 1){
			dp[i] -= 1;
		}

		pre[i] = (pre[i - 1] + dp[i]) % MOD;
	}



	ll ans = (dp[n - 1] + (n - 1) * (n - 1) + 1) % MOD;
	for(int i = 1; i < n; i++){
		ans = (ans + dp[i - 1] * (i + (i < n - 1))) % MOD;
	}


	for(int i = 1; i < n - 1; i++){
		ans = (ans + ((dp[i - 1] * (n - 1)) % MOD) * (n - 1)) % MOD;
	}
	cout << ans - (n == 1) << endl;

}


Measured memory_bytes: 15872
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int N,K;cin>>N>>K;
  
  if(N%K==0){
    cout<<0<<endl;
  }
  else{
    cout<<1<<endl;
  }
}

Measured memory_bytes: 3632
using System;
using System.Collections.Generic;

class Program
{
	static void Main(string[] args)
	{
		string[] input = Console.ReadLine().Split(' ');
		int n = int.Parse(input[0]);
		int[] cnt = new int[100001];
		input = Console.ReadLine().Split(' ');
		for(int i=0; i<n; i++) cnt[int.Parse(input[i])] += 1;
		long ans = 0;
		for(int i = 0; i < 100001; i++) ans += (long)cnt[i] * (long)i;

		input = Console.ReadLine().Split(' ');
		int q = int.Parse(input[0]);
		for(int query = 0; query < q; query++)
		{
			input = Console.ReadLine().Split(' ');
			int b = int.Parse(input[0]);
			int c = int.Parse(input[1]);
			int cntB = cnt[b];
			ans += ((long)c-(long)b) * (long)cntB;
			cnt[c] += cntB;
			cnt[b] = 0;
			Console.WriteLine(ans);
		}
	}
}


Measured memory_bytes: 46048
# coding:utf-8

import math

def main():
    p,q,r = map(int, raw_input().split())
    m = max(p,q,r)
    total = 0
    if p <= q and r <= q:
        total = p + r
    if q <= r and p <= r:
        total = p + q
    if r <= p and q <= p:
        total = q + r
    print total

if __name__ == "__main__":
    main()



Measured memory_bytes: 2568
#include <stdio.h>

int main(void)
{
    int N, i, j, minj, temp;
    int count = 0;
    int A[100];

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

    for (i = 0; i < N; i++){
        minj = i;
        for ( j = i; j < N; j++){
            if (A[j] < A[minj])
            minj = j;}
        if ( minj != i){
        temp = A[i];
        A[i] = A[minj];
        A[minj] = temp;
        count++;
        }
    }

    for (i = 0; i < N; i++){
		if ( i != 0)
		printf(" ");
		
        printf("%d", A[i]);
    }

    printf("\n%d\n", count);

    return 0;
}


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

public class Main {
    static ContestScanner in;
    static Writer out;
    public static void main(String[] args) {
        Main main = new Main();
        try {
            in = new ContestScanner();
            out = new Writer();
            main.solve();
            out.close();
            in.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    void solve() throws IOException {
        int a = 0;
        for (int i = 0; i < 3; i++) {
            a *= 10;
            a += in.nextInt();
        }
        System.out.println(a % 4 == 0 ? "YES" : "NO");
    }

}

@SuppressWarnings("serial")
class MultiSet<T> extends HashMap<T, Long>{
    @Override public Long get(Object key){return containsKey(key)?super.get(key):0L;}
    public void add(T key,long v){put(key,get(key)+v);}
    public void add(T key){put(key,get(key)+1);}
    public void sub(T key){final long v=get(key);if(v==1)remove(key);else put(key,v-1);}
    public MultiSet<T> merge(MultiSet<T> set)
    {MultiSet<T>s,l;if(this.size()<set.size()){s=this;l=set;}else{s=set;l=this;}
        for(Entry<T,Long>e:s.entrySet())l.add(e.getKey(),e.getValue());return l;}
}

class Writer extends PrintWriter{
    public Writer(String filename)throws IOException
    {super(new BufferedWriter(new FileWriter(filename)));}
    public Writer()throws IOException{super(System.out);}
}
class ContestScanner implements Closeable{
    private BufferedReader in;private int c=-2;
    public ContestScanner()throws IOException
    {in=new BufferedReader(new InputStreamReader(System.in));}
    public ContestScanner(String filename)throws IOException
    {in=new BufferedReader(new InputStreamReader(new FileInputStream(filename)));}
    public String nextToken()throws IOException {
        StringBuilder sb=new StringBuilder();
        while((c=in.read())!=-1&&Character.isWhitespace(c));
        while(c!=-1&&!Character.isWhitespace(c)){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public String readLine()throws IOException{
        StringBuilder sb=new StringBuilder();if(c==-2)c=in.read();
        while(c!=-1&&c!='\n'&&c!='\r'){sb.append((char)c);c=in.read();}
        return sb.toString();
    }
    public long nextLong()throws IOException,NumberFormatException
    {return Long.parseLong(nextToken());}
    public int nextInt()throws NumberFormatException,IOException
    {return(int)nextLong();}
    public double nextDouble()throws NumberFormatException,IOException
    {return Double.parseDouble(nextToken());}
    public void close() throws IOException {in.close();}
}


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

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

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

#define CHMIN(a, b) (a) = min((a), (b))
#define CHMAX(a, b) (a) = max((a), (b))

#define DEBUG(x) cout << #x << ": " << (x) << endl
#define PRINT(x) cout << x << endl
#define all(x) x.begin(),x.end()


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

    cout << a-b+1 << endl;
}



Measured memory_bytes: 256
let l = read_int ()
let s = float_of_int (l/3)
let _ = (if l mod 3 = 0 then s ** 3. else
        if l mod 3 = 1 then (s +. 0.333333333) *. (s +. 0.333333333) *. (s +. 0.333333334) else
        (s +. 0.666666667) *. (s +. 0.666666666) *. (s +. 0.666666667)) |> Printf.printf "%f\n"

Measured memory_bytes: 384
fun main() {
    val input = readLine()!!.split(" ").map { it.toInt() }
    val a = input[0]
    val b = input[1]
    val c = input[2]
    val d = input[3]
    val e = input[4]
    val f = input[5]

    val iMax = f / (a * 100)
    val jMax = f / (b * 100)
    val kMax = f / c
    val lMax = f / d

    var max = 0.0
    var answerSugarWater = 0
    var answerSugar = 0

    for (i in (0..iMax)) {
        for (j in (0..jMax)) {
            val water = 100 * a * i + 100 * b * j
            if (water in 1 until f) {
                for (k in (0..kMax)) {
                    for (l in (0..lMax)) {
                        val sugar = c * k + d * l
                        val total = water + sugar
                        val density = sugar * 100.0 / water
                        if (total <= f && density <= e.toDouble() && max <= density) {
                            max = density
                            answerSugarWater = total
                            answerSugar = sugar
                        }
                    }
                }
            }
        }
    }

    print("$answerSugarWater $answerSugar")
}

Measured memory_bytes: 36864
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

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

int d[205][205], r[10];
signed main(void)
{
  int n, m, R;
  cin >> n >> m >> R;
  REP(i, R) cin >> r[i], r[i]--;
  REP(i, n) REP(j, n) d[i][j] = INF;
  REP(i, n) d[i][i] = 0;
  REP(i, m) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    d[a][b] = d[b][a] = c;
  }
  REP(k, n) REP(i, n) REP(j, n) chmin(d[i][j], d[i][k]+d[k][j]);

  sort(r, r+R);
  int ans = INF;
  do {
    int ret = 0;
    FOR(i, 1, R) {
      // cout << r[i] << " ";
      ret += d[r[i]][r[i-1]];
    }
    // cout << endl << ret << endl;
    chmin(ans, ret);
  } while(next_permutation(r, r+R));
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+5,mod=1e9+7;
ll d[5005];
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll k,q;cin>>k>>q;
    for(ll i=0;i<k;i++)cin>>d[i];
    for(ll n,x,m;q>0;q--){
        cin>>n>>x>>m;
        x%=m;
        ll zeroes=0,sum=x;
        for(ll i=0;i<k;i++){
            ll val = d[i]%m;
            ll cnt = (n-1)/k;
            if((n-1)%k>i)cnt++;
            if(val==0)zeroes+=cnt;
            else sum+=cnt*val;
        }
        ll ans = sum/m - x/m + zeroes;
        cout<<(n-1)-ans<<"\n";
    }
}

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

typedef priority_queue<int> maxHeap;
typedef priority_queue<int, vector<int>, greater<int>> minHeap;
#define endl "\n"
#define int long long
#define MOD 1000000007
#define PI 3.1415926535897932384626433832795
#define max(x, y) ((x > y) ? x : y)
#define min(x, y) ((x < y) ? x : y)
#define mid(s, e) ((s + (e - s) / 2))

bool test_cases;

void init(bool k) {
    test_cases = k;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

struct precompute {
    void compute() {
    }
};

double dp[3000][3000];

struct test_cases {
    double aagekiProb(double a[], int n, int i, int tailsReq, int curHeads, int curTails) {
        if (i == n) {
            return 1;
        }
        if (dp[curHeads][curTails] != 2.000) {
            return dp[curHeads][curTails];
        }
        if (curTails == tailsReq) {
            double k2 = a[i] * aagekiProb(a, n, i + 1, tailsReq, curHeads + 1, curTails);
            double k3 = 0;
            dp[curHeads + 1][curTails] = k2 / a[i];
            return dp[curHeads][curTails] = k3 + k2;
        } else {
            double k2 = a[i] * aagekiProb(a, n, i + 1, tailsReq, curHeads + 1, curTails);
            double k3 = (1 - a[i]) * aagekiProb(a, n, i + 1, tailsReq, curHeads, curTails + 1);
            dp[curHeads][curTails + 1] = k3 / (1 - a[i]);
            dp[curHeads + 1][curTails] = k2 / a[i];
            return dp[curHeads][curTails] = k3 + k2;
        }
    }

    void test_case() {
        int n;
        cin >> n;
        for (int i = 0; i < 3000; i++) {
            for (int j = 0; j < 3000; j++) {
                dp[i][j] = 2.000;
            }
        }
        double a[n];
        for (int i = 0; i < n; i++) cin >> a[i];

        cout << fixed << setprecision(10) << aagekiProb(a, n, 0, n / 2, 0, 0) << endl;
    }
};

int32_t main() {
    init(false);
    int tc;
    if (test_cases) {
        cin >> tc;
    } else {
        tc = 1;
    }
    struct precompute l;
    l.compute();
    for (int i = 0; i < tc; i++) {
        struct test_cases o;
        o.test_case();
    }
    return 0;
};

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

#define ll long long
#define ull unsigned long long

#define pii pair < int, int >
#define pll pair < ll, ll >
#define pci pair < char, int >
#define psi pair < string, int >

#define vi vector < int >
#define vll vector < ll >
#define vs vector < string >
#define vc vector < char >
#define pvi vector < pii >
#define pvll vector < pll >

#define pb push_back

#define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

using namespace std;

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

int main()
{
    fast;

    int n;

    cin >> n;

    int a[n + 5], cnt = 0;

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

        if(i % 2 == 1 && a[i] % 2 == 1) cnt++;
    }

    cout << cnt << endl;

    return 0;
}



Measured memory_bytes: 3580
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int par[2020];
int now[2020];
vector<int>ans;
void apply(int node)
{
	ans.push_back(node);
	int t = now[node];
	now[node] = now[0];
	for (;;)
	{
		if (node == 0)break;
		node = par[node];
		int s = now[node];
		now[node] = t;
		t = s;
	}
}
void check(int num)
{
	for (int i = 0; i < num; i++)if (i != now[i])return;
	printf("%d\n", ans.size());
	for (int i = 0; i < ans.size(); i++)printf("%d\n", ans[i]);
	exit(0);
}
vector<int>ko[2020];
int siz[2020];
int dep[2020];
int heavyko[2020];
int col[2020];
int hldep[2020];
int pt = 1;
bool flag[2020];
bool allflag[2020];
void dfs1(int node, int d)
{
	int s = 1;
	dep[node] = d;
	int maxi = 0, rr = -1;
	for (int i = 0; i < ko[node].size(); i++)
	{
		dfs1(ko[node][i], d + 1);
		s += siz[ko[node][i]];
		if (siz[ko[node][i]]>maxi)maxi = siz[ko[node][i]], rr = ko[node][i];
	}
	heavyko[node] = rr;
	siz[node] = s;
}
void dfs2(int node, int c, int d)
{
	col[node] = c;
	hldep[c] = d;
	for (int i = 0; i < ko[node].size(); i++)
	{
		if (ko[node][i] == heavyko[node])dfs2(ko[node][i], c, d);
		else
		{
			pt++;
			dfs2(ko[node][i], pt - 1, d + 1);
		}
	}
}
int main()
{
	int num;
	scanf("%d", &num);
	for (int i = 1; i < num; i++)scanf("%d", &par[i]), ko[par[i]].push_back(i);
	for (int i = 0; i < num; i++)scanf("%d", &now[i]);
	dfs1(0, 0);
	dfs2(0, 0, 0);
	int maxdep = 0;
	for (int i = 0; i < pt; i++)maxdep = max(maxdep, hldep[i]);
	for (int p = maxdep; p >= 0; p--)
	{
		fill(flag, flag + num, false);
		for (int i = 0; i < num; i++)if (hldep[col[i]]>p)flag[i] = true;
		for (;;)
		{
			//printf("%d  ", p);
			//for (int i = 0; i < num; i++)printf("%d ", now[i]); printf("\n");
			check(num);
			bool fff = true;
			for (int i = 0; i < num; i++)if (!flag[i])fff = false;
			if (fff)break;
			if (hldep[col[now[0]]] == p)
			{
				int rr = -1;
				for (int i = 0; i < num; i++)
				{
					if (col[now[0]] == col[i])rr = i;
				}
				int newflag = -1, piv = rr;
				for (;;)
				{
					if (!allflag[rr])
					{
						allflag[rr] = true;
						flag[rr] = true;
						break;
					}
					if (now[0] < now[rr])piv = par[rr];
					rr = par[rr];
				}
				apply(piv);
			}
			else
			{
				int rr = -1;
				for (int i = 0; i < num; i++)
				{
					if (flag[i])continue;
					rr = i;
				}
				apply(rr);
				flag[rr] = true;
			}
		}
	}
}

Measured memory_bytes: 768
#include<stdio.h>
int main(void){
int n,m,l,A[100][100],B[100][100],a,b,k;
long long int C[100][100];
scanf("%d %d %d",&n,&m,&l);
for(a=0;a<100;a++)for(b=0;b<100;b++)C[a][b]=0;
for(a=0;a<n;a++)for(b=0;b<m;b++)scanf("%d",&A[a][b]);
for(a=0;a<m;a++)for(b=0;b<l;b++)scanf("%d",&B[a][b]);
for(a=0;a<n;a++)for(b=0;b<l;b++)for(k=0;k<m;k++)C[a][b]+=A[a][k]*B[k][b];
for(a=0;a<n;a++){
for(b=0;b<l;b++){
printf("%lld",C[a][b]);
if(b!=l-1)printf(" ");
}
printf("\n");
}
return 0;
}


Measured memory_bytes: 2104
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

N, W = na()
maxV = 10 ** 5
dp = [[10**9+7] * (maxV+1) for i in range(N+1)]  # dp[i][v] i番目までで価値がvの時の重さの合計の最小値
dp[0][0] = 0
tp = [na() for i in range(N)]
list.sort(tp, key=lambda x:x[0])
for i in range(1, N+1):
    wi, vi = tp[i - 1]
    for v in range(1, maxV+1):
        if v - vi >= 0:
            dp[i][v] = min(dp[i - 1][v], dp[i - 1][v - vi] + wi)
        else:
            dp[i][v] = dp[i - 1][v]
ans = -1
for i in range(1, N + 1):
    for v in range(1, maxV+1):
        if dp[i][v] <= W:
            ans = max(ans, v)
print(ans)

Measured memory_bytes: 119660
import sys
import math
from collections import deque
import heapq as hq

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N = NI()
    planes = [list(SI().split()) for _ in range(N)]

    XS = [[] for _ in range(200001)]
    YS = [[] for _ in range(200001)]
    ZS = [[] for _ in range(400001)]
    WS = [[] for _ in range(400001)]
    for plane in planes:
        x, y, u = int(plane[0]), int(plane[1]), plane[2]
        XS[x].append((y, u))
        YS[y].append((x, u))
        ZS[x+y].append((x, u))
        WS[x-y+200000].append((x, u))
    for X in XS:
        hq.heapify(X)
    for Y in YS:
        hq.heapify(Y)
    for Z in ZS:
        hq.heapify(Z)
    for W in WS:
        hq.heapify(W)

    ans = float("inf")

    for X in XS:
        if len(X) <= 1:
            continue
        c = -1
        for _ in range(len(X)):
            k, u = hq.heappop(X)
            if u == "U":
                c = k
            if u == "D" and c >= 0:
                ans = min(ans, (k - c)*5)
                c = -1

    for Y in YS:
        if len(Y) <= 1:
            continue
        c = -1
        for _ in range(len(Y)):
            k, u = hq.heappop(Y)
            if u == "R":
                c = k
            if u == "L" and c >= 0:
                ans = min(ans, (k - c)*5)
                c = -1

    for Z in ZS:
        if len(Z) <= 1:
            continue
        c = -1
        d = -1
        for _ in range(len(Z)):
            k, u = hq.heappop(Z)
            if u == "R":
                c = k
            if u == "D":
                d = k
            if u == "U" and c >= 0:
                ans = min(ans, (k - c)*10)
                c = -1
            if u == "L" and d >= 0:
                ans = min(ans, (k - d)*10)
                d = -1

    for W in WS:
        if len(W) <= 1:
            continue
        c = -1
        d = -1
        for _ in range(len(W)):
            k, u = hq.heappop(W)
            if u == "R":
                c = k
            if u == "U":
                d = k
            if u == "D" and c >= 0:
                ans = min(ans, (k - c)*10)
                c = -1
            if u == "L" and d >= 0:
                ans = min(ans, (k - d)*10)
                d = -1

    if ans == float("inf"):
        print("SAFE")
    else:
        print(ans)


if __name__ == "__main__":
    main()

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

using namespace std;

int main() {
  string str;
  int counter[26] = {0};
  while(getline(cin, str)){
    for(unsigned int i = 0; i < str.size(); i++){
      if      ('a' <= str[i] && str[i] <= 'z') counter[str[i] - 'a']++;
      else if ('A' <= str[i] && str[i] <= 'Z') counter[str[i] - 'A']++;
    }
  }
  for(unsigned int i = 0; i < extent<decltype(counter),0>::value; i++){
    cout << (char)('a'+i) << " : " << counter[i] << endl;
  }
  return 0;
}



Measured memory_bytes: 3212
#include"bits/stdc++.h"
#include"math.h"
using namespace std;

int main(){
int a;scanf("%d",&a);
int L=a/100;
int R=a%100;
if(1<=L&&L<=12){
if(1<=R&&R<=12)printf("AMBIGUOUS\n");
else printf("MMYY\n");
}else{
if(1<=R&&R<=12)printf("YYMM\n");
else printf("NA\n");
}
}

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

public class Test
{
	public static void Main()
	{
		// my code goes here
		
		var a = Console.ReadLine().Split().Select(nyan => int.Parse(nyan)).ToArray();
		int n = a[0];
		int r = a[1];
		if(n>=10){
			Console.WriteLine(r);
		}else{
			Console.WriteLine(r+ 100*(10-n));
		}
		
		
	}
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
//#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl


signed main(void){
    int A,B,M;
    int a[114514],b[114514];
    int x[114514],y[114514],c[114514];
    int amn=INF,bmn=INF;
    cin >> A >> B >> M;
    REP(i,A){
        cin >> a[i];
        amn=min(amn,a[i]);
    }
    REP(i,B){
        cin >> b[i];
        bmn=min(bmn,b[i]);
    }
    REP(i,M){
        cin >> x[i] >> y[i] >> c[i];
        x[i]--;y[i]--;
    }
    
    int Ans=amn+bmn;
    REP(i,M){
        Ans=min(Ans,a[x[i]]+b[y[i]]-c[i]);
    }
    cout << Ans << endl;
    return 0;
}



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

using namespace std;

int main(void){
	int m, n, a[2000], total = 0;

	cin >> n >> m;

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

	int threshold = (4 * m);

	for(int i = 0; i < n; i++){
		if((a[i] * threshold) >= total){
			m--;
		}
	}

	if(m <= 0){
		cout << "Yes";
	}
	else{
		cout << "No";
	}

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
char s[105];
int check(int m,int n){
	int i,j;
	for(i=m,j=n;i!=j&&i<j;i++,j--)
		if(s[i]!=s[j])
			return 0;
	return 1;
}
int main()
{
	int m=0,n=0,l,r,p=0;
	scanf("%s",s);
	l=0;r=strlen(s)-1;
	p=check(l,r);
	l=((strlen(s)+3)/2)-1;r=strlen(s)-1;
	m=check(l,r);
	l=0;r=((strlen(s)-1)/2)-1;
	n=check(l,r);
	if(n&m&&p)
		printf("Yes",n,m);
	else printf("No"); 
}

Measured memory_bytes: 128
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1000000007,inv2=500000004;
inline void add(int &x,int y){(x+=y)>=mod?x-=mod:0;}
inline int pl(int x,int y){return (x+=y)>=mod?x-mod:x;}
int n,q,a[3030],x[3030],y[3030],dp[3030][3030],tmp[3030][3030],ans;
int main()
{
	scanf("%d %d",&n,&q);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=q;++i)scanf("%d %d",&x[i],&y[i]);
	for(int i=1;i<=n;++i)for(int j=1;j<i;++j)dp[i][j]=1;
	for(int i=q;i;--i)
	{
		for(int j=1;j<=n;++j)
		{
			tmp[x[i]][j]=1ll*dp[x[i]][j]*inv2%mod;
			tmp[y[i]][j]=1ll*dp[y[i]][j]*inv2%mod;
			tmp[j][x[i]]=1ll*dp[j][x[i]]*inv2%mod;
			tmp[j][y[i]]=1ll*dp[j][y[i]]*inv2%mod;
		}
		for(int j=1;j<=n;++j)
		{
			dp[y[i]][j]=dp[x[i]][j]=pl(tmp[x[i]][j],tmp[y[i]][j]);
			dp[j][x[i]]=dp[j][y[i]]=pl(tmp[j][x[i]],tmp[j][y[i]]);
		}
		dp[x[i]][y[i]]=dp[y[i]][x[i]]=pl(tmp[x[i]][y[i]],tmp[y[i]][x[i]]);
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			if(a[i]<a[j])add(ans,dp[i][j]);
	for(int i=1;i<=q;++i)add(ans,ans);
	printf("%d",ans);
	return 0;
}


Measured memory_bytes: 71936
#include<bits/stdc++.h>
using namespace std;
set<long long> v;
void dfs(int k,long long x)
{
	v.insert(x);
	if(k>=9)return;
	int a=x%10;
	if(a)
		dfs(k+1,x*10+a-1);
	dfs(k+1,x*10+a);
	if(a!=9)
		dfs(k+1,x*10+a+1);
}
int main()
{
	for(int i=1;i<=9;i++)
		dfs(0,i);
	int k;
	cin>>k;
	for(int i=0;i<k-1;i++)
		v.erase(v.begin());
	cout<<*v.begin()<<endl;
	return 0;
}

Measured memory_bytes: 9600
<?php
fscanf(STDIN, '%d %d', $cnt, $lim);
fscanf(STDIN, '%d %d %d', $score['goo'], $score['cho'], $score['paa']);
fscanf(STDIN, '%s', $str);
$ans = 0;
$pats = str_split($str);

for ($i=0; $i < $cnt; $i++) {
    $next = $pats[$i];
    switch ($next) {
        case 'r':
            $tar = 'paa';
            break;

        case 's':
            $tar = 'goo';
            break;

        case 'p':
            $tar = 'cho';
            break;
            

        default:
            break;
    }

    if ($i <= $lim - 1) {
        $ans += $score[$tar];
    } else {
        if ($pats[$i - $lim] !== $next) {
            $ans += $score[$tar];
        }
        if ($pats[$i - $lim] !== 'n' && $pats[$i - $lim] === $next) {
            $pats[$i] = 'n';
        }
    }
}

echo $ans . "\n";

Measured memory_bytes: 10744
from collections import Counter

n, q = map(int, input().split())
c = Counter()
for _ in range(q):
    u, v = map(int, input().split())
    c[u] += 1
    c[v] += 1

safe = all(c[x] % 2 == 0 for x in c)
print('YES' if safe else 'NO')

Measured memory_bytes: 9448
D = map(int, open(0).read().split()[:-2])
for n, x in zip(*[iter(D)]*2):
    ans = 0
    for i in range(1, n+1):
        for j in range(i+1, n+1):
            if j >= x - i - j:
                break
            if x - i - j not in (i, j) and x - i - j <= n:
                ans += 1
    print(ans)


Measured memory_bytes: 5596
#include <iostream>
#include <string>
#include <cctype>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map> // pair
#include <set>
#define MAXSIZE 200000
#define PI 3.141592653589
using namespace std;

template<typename T>
T add(T a,T b){
  return a+b;
}

namespace A
{
  int f(void){
    return 1;
  }
}

int main(){
  int a,b,c,d,e,f;
  while (std::cin >> a>>b>>c>>d>>e>>f) {
    double x=(1.0)*(b*f-c*e)/(b*d-a*e);
    double y=(1.0)*(c*d-a*f)/(b*d-a*e);
    if(x>-0.001&&x<0.001)x=0.000;
    if(y>-0.001&&y<0.001)y=0.000;
    printf("%.3f %.3f\n",x,y);
  }

}



Measured memory_bytes: 3108
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1e9+7;
signed main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    cout<<((a+d-1)/d>=(c+b-1)/b?"Yes":"No")<<endl;
}

Measured memory_bytes: 3632
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = list(map(int, list(sr())))
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += i+1
        print(ans)
        return
    S = S[::-1]
    lp = [0]*P
    c = 0
    for i in range(N):
        d = S[i]*pow(10,i,P)
        c = (c+d)%P
        lp[c] += 1
    ans = lp[0]
    for i in range(P):
        ans += lp[i]*(lp[i]-1)//2
    print(ans)
resolve()

Measured memory_bytes: 6560
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int h, w;
  cin >> h >> w;
  cout << string(w + 2, '#') << endl;
  rep(i, 0, h) {
    string s;
    cin >> s;
    cout << '#';
    rep(j, 0, w) cout << s[j];
    cout << '#' << endl;
    ;
  }

  cout << string(w + 2, '#') << endl;
}


Measured memory_bytes: 256