akhauriyash/Code-Regression huggingface dataset:
// #ifdef DEBUG
// #define _GLIBCXX_DEBUG
// #endif
#include <iostream>
#include <iomanip>
#include <vector>
#include <valarray>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <bitset>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <complex>
#include <string>
#include <sstream>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>

// these require C++11
#include <unordered_set>
#include <unordered_map>
#include <random>
#include <thread>
#include <chrono>

using namespace std;

#define int long long
#define var auto
#define val const auto

#define all(c) c.begin(), c.end()
#define repeat(i, n) for (int i = 0; i < static_cast<int>(n); i++)
#define debug(x) #x << "=" << (x)

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

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

typedef complex<double> point;

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

template <typename T>
set<T> operator|(const set<T>& a,const set<T>& b){
    set<T> s = a;
    s.insert(b.begin(),b.end());
    return s;
}
vector<string> split_with_delim(const string& s,char delim){
    istringstream ss(s);
    vector<string> ret;
    string tmp;
    while(getline(ss,tmp,delim)){
        ret.push_back(tmp);
    }
    return ret;
}

set<string> get_member(const string& here,map<string,vector<string> >& children,
                       set<string>& already_added){
    if(already_added.find(here) != already_added.end()) return {};
    already_added.insert(here);
    if(children.find(here) == children.end()){
        return {here};
    }else{
        set<string> ret;
        for(string s : children[here]){
            ret = ret | get_member(s,children,already_added);
        }
        return ret;
    }
}

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

    while(true){
        map<string,vector<string> > children;
        int n;cin >> n;
        if(n == 0) break;
        cin.ignore();
        string search;
        for(int i=0;i<n;i++){
            string s; cin >> s;
            s = s.substr(0,s.size()-1); // .
            val v = split_with_delim(s,':');
            val group = v[0];
            val member = split_with_delim(v[1],',');
            children[group] = member;
            if(i == 0) search = group;
        }

        set<string> checked;
        set<string> member = get_member(search,children,checked);
        cout << member.size() << endl;
    }
    return 0;
}

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

int main()
{
    int N;
    cin >> N;
    vector<int> p(N);
    rep(i, N)
    {
        cin >> p[i];
    }
    int ans = 0;

    rep(i, N - 1)
    {
        if (p[i] == i + 1 && p[i + 1] == i + 2)
        {
            ans++;
            swap(p[i], p[i + 1]);
        }
    }

    rep(i, N)
    {
        if (p[i] == i + 1)
            ans++;
    }

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

Measured memory_bytes: 640
n, m = map(int, input().split())
nList = ['*'] * n
flag = True
for i in range(m):
    s, c = map(int, input().split())
    if nList[s-1] == '*':
        nList[s-1] = str(c)
    elif nList[s-1] != str(c):
        flag = False
        break
if nList[0] == '0' and n > 1:
    flag = False
if flag:
    for i, num in enumerate(nList):
        if num == '*':
            if i == 0 and n > 1:
                nList[i] = '1'
            else:
                nList[i] = '0'
    print(''.join(nList))
else:
    print('-1')

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

int main(){
  int K, X;
  cin >> K >> X;
  
  int strt, goal;
  
  strt = X - K + 1;
  goal = X + K - 1;
  
  for (int i = strt; i <= goal; i++) {
    cout << i << ' ';
  }
    
  return 0;
}

Measured memory_bytes: 256
#include <bits//stdc++.h>
using namespace std;
#define rep(i,n,k) for(int i=n;i<k;i++)
#define int long long
#define F first 
#define S second
#define P make_pair 

signed main(void){
    int ans=0;
    int n,m,q,p;
    string s;
    cin>>n;
    cin>>s;
    string a;
    rep(i,0,52){
        m='A'+(i%26);
        a+=m;
    }
    rep(i,0,s.size()){
        m=s[i]-'A'+n;
        cout<<a[m];
    }
    cout<<endl;
    
}


Measured memory_bytes: 256
import Data.List

func n (x:xs)
    | n > 0 = x + func (n-1) xs
    | otherwise = 0
func n [] = 0

main :: IO ()
main = do
    [n, k] <- map read . words <$> getLine :: IO [Int]
    h <- map read . words <$> getLine :: IO [Int]
    print $ func (n-k) (sort h)

Measured memory_bytes: 96636
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
#include <cmath>
#include <limits>
#include <type_traits>
#include <iomanip>
using namespace std;

using INT = long long;
using UINT = unsigned long long;

unsigned gcd(unsigned a, unsigned b) {
	while (1) {
		if (a < b) swap(a, b);
		if (!b) break;
		a %= b;
	}
	return a;
}

int main()
{
	int n;
	cin >> n;
	vector<INT> p(n);
	for (size_t i = 0; i < n; i++)
	{
		cin >> p[i];
	}
	sort(p.begin(), p.end());

	INT up = p[n / 2];
	INT btm = p[n / 2 - 1];

	cout << up - btm << endl;
}


Measured memory_bytes: 1024
#include<stdio.h>

int main(){
   int x[5];
   scanf("%d %d %d %d %d", &x[0], &x[1], &x[2], &x[3], &x[4]);

   for(int i=0; i<5; i++){
      if(x[i] == 0){
         printf("%d\n", i+1);
      }
   }

   return 0;
}


Measured memory_bytes: 1696
#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define lli long long int
using namespace std;
#define S second
#define F first
#define pb push_back 
#define M1 1000000007
#define M2 998244353
#define plli pair<lli,lli>
#define setit set<lli>::iterator seti
#define mapit map<lli,lli> ::iterator mapi
#define MP make_pair
#define MT make_tuple
// map      iterator->first  iterator.first
// map      mp[key]=value
// set      *s.begin()
// vector   v[j]=value
// pair     p.first p.second
// vector of pairs v[j].first v[j].second
// tuple    get<index>(tuple_name)
// vector of tuples get<index>(v[j])  sort(v.begin(),v.end())
//priority queue .top() .pop() .push()
// __gcd(x,y)
#define fr(j,a,b) for(j=a;j<b;j++)

int power(int x, unsigned int y, int p)  
{    int res = 1;    
     x = x % p;
     if (x == 0) return 0;
     while (y > 0)  
     {  if (y & 1)  
        res = (res*x) % p;  
        y = y>>1;
        x = (x*x) % p;  
     }  
    return res;  
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    lli t,i,j,n,a,b,c,k,x,d,e,f;
    cin>>a>>b>>c>>k;
    if(k>a){d=a;}
        else{d=k;cout<<d;return 0;}
    x=d;
    if(b<k-d){e=b;}
        else{b=k-d;cout<<x;return 0;}
    if(c<k-d-e){f=c;}
        else{f=k-d-e;}
    if(f<=0){cout<<x;return 0;}
    x=x-f;
    cout<<x;
}

Measured memory_bytes: 3640
import java.util.Scanner;


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

		int N = sc.nextInt();

		int K = sc.nextInt();

		String S = sc.next();

		String[] str = new String[N];

		for(int i=0; i<N; i++) {

			if(i==K-1) {
				if( String.valueOf(S.charAt(i)) .equals( "A")) str[i] = "a";
				else if( String.valueOf(S.charAt(i)).equals( "B"))  str[i] =  "b";
				else if( String.valueOf(S.charAt(i)) .equals( "C"))  str[i] =  "c";
			}
			else {
			str[i] = String.valueOf(S.charAt(i));

			}

		}
		for(int i=0; i<N; i++) {


		System.out.print(str[i]);
		}
	}

}


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

#define lint long long
#define P pair<int, int>
#define LLP pair<long long, long long>
#define REP(i, x, n) for(int i = (x), i##_len = (int)(n) ; i < i##_len ; ++i)
#define rep(i, n) for(int i = 0, i##_len = (int)(n) ; i < i##_len ; ++i)
#define repr(i, n) for(int i = (int)(n) - 1 ; i >= 0 ; --i)
#define SORT(x) sort((x).begin(), (x).end())
#define SORT_INV(x) sort((x).rbegin(), (x).rend())

const int IINF = 1e9 + 100;
const long long LLINF = 2e18 + 129;
const long long MOD = 1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};
const double EPS = 1e-8;

int b, c, d;
lint memo[1001][1001];
lint perm[1001][1001];
lint fact[1001];
lint inv[1001];

long long power(long long x, long long n){
    long long res = 1;
    x %= MOD;
    while(n > 0LL){
        if(n & 1LL){
            res *= x;
            res %= MOD;
        }
        x *= x;
        x %= MOD;
        n >>= 1;
    }
    return res;
}

lint factorial(lint n){
    if(fact[n] >= 0LL){
        return fact[n];
    }
    if(n == 0LL){
        return 1LL;
    }

    return fact[n] = n * factorial(n - 1) % MOD;
}

lint inv_fact(lint n){
    if(inv[n] >= 0LL){
        return inv[n];
    }

    return inv[n] = power(factorial(n), MOD - 2);
}

lint nPr(lint n, lint r){
    if(perm[n][r] >= 0LL){
        return perm[n][r];
    }

    return perm[n][r] = factorial(n) * power(factorial(n - r), MOD - 2) % MOD;
}

lint solve(int n, int a){
    if(n == 0){
        return 1LL;
    }
    if(n < 0 || a > b){
        return 0LL;
    }
    if(memo[n][a] >= 0LL){
        return memo[n][a];
    }

    lint res = solve(n, a + 1);

    for(int i = c ; i <= d ; ++i){
        if(i * a > n){
            break;
        }
        res += ((solve(n - i * a, a + 1) * nPr(n, i * a) % MOD) * power(power(factorial(a), i), MOD - 2) % MOD) * inv_fact(i) % MOD;
        res %= MOD;
    }

    return memo[n][a] = res;
}

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

    int n, a;
    cin >> n >> a >> b >> c >> d;

    fill(memo[0], memo[n + 1], -1LL);
    fill(perm[0], perm[1001], -1LL);
    fill(fact, fact + 1001, -1LL);
    fill(inv, inv + 1001, -1LL);

    lint ans = solve(n, a);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 16128
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long int n;
  cin>>n;
  long int a[n],b[n];
  for(int i=0;i<n;i++){
    cin>>a[i]; b[i]=a[i];}
  sort(a,a+n);
  for(int i=0;i<n;i++)
  {
    if(b[i]==a[n-1])
      cout<<a[n-2]<<endl;
     else
    cout<<a[n-1]<<endl;
   }
}

Measured memory_bytes: 4736
#include<stdio.h>
int main(){
  int x,y;
  for(;;){
    scanf("%d %d",&x,&y);
    if(x==0&&y==0)break;
    if(x<y){printf("%d %d\n",x,y);
    }else{
      printf("%d %d\n",y,x);
    }
  }
  return 0;
}

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

typedef long long ll;
typedef vector<ll> vll;
const ll MOD = 1e9 + 7;

int main() {
    ll n, m;
    cin >> n >> m;
    vll nums(n + 1);
    unordered_map<ll, ll> hashMap;
    hashMap[0] = 1;
    ll left = 0;
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> nums[i];
        nums[i] += nums[i - 1];
        left = nums[i] % m;
        if (hashMap.find(left) == hashMap.end()) {
            hashMap[left] = 1;
        } else {
            ans += hashMap[left]++;
        }
    }
    cout << ans << endl;
    return 0;
}

static int speedUp = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();

Measured memory_bytes: 4492
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;

int N;
string s;
int cnt_g,cnt_p;
int main(){
    cin>>s;
    N = s.length();
    cnt_g=0;cnt_p=0;
    int ans=0;
    for(int i=0;i<N;i++){
        if(cnt_g==cnt_p){
            ++cnt_g;
            if(s[i]=='p') --ans;
        }
        else {
            ++cnt_p;
            if(s[i]=='g')  ++ans;
        }
    }
    printf("%d\n",ans);
    getchar();
    getchar();

    return 0;

}

Measured memory_bytes: 512
n = int(input())
List = list(input())
count = List.count("R") * List.count("G") *List.count("B")
for w in range(1, n // 3 * 3 + 1):
    for s in range(n - 2 * w):
        if List[s] != List[s + w] and List[s] != List[s + w * 2] and List[s + w] != List[s + w * 2]:
            count -= 1
print(count)

Measured memory_bytes: 9208
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main(){
  string S;
  cin >> S;
  int ans01=0;
  int ans10=0;
  for(int i=0; S[i] != '\0'; i++){
    if(i%2==0){
      if(S[i] == '0'){
        ans10++;
      }
      else ans01++;
    }
    else{
      if(S[i] == '0'){
        ans01++;
      }
      else ans10++;
    }
  }
  cout << min(ans01, ans10);
  return 0;
}


Measured memory_bytes: 512
#include<stdio.h>
#include<stdlib.h>
 
int main(void) {
  char s[64], *w;
  int sheep, wolf, i = 0;
  
  scanf("%[^\n]", s);

  while (s[i++] != ' ');
  s[--i] = '\0';
  w = &s[++i];

  sheep = atoi(s);
  wolf = atoi(w);
  
  if (sheep > wolf) {
    printf("safe");
  } else {
    printf("unsafe");
  }
  
  return 0;
}

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

object Main extends App {
  val inputs = StdIn.readLine().split(" ")
  val N = inputs(0).toInt
  val Y = inputs(1).toInt

  if (Y > N * 10000 || Y < N * 1000) {
    println("-1 -1 -1")
  } else {
    val max_10000 = Y / 10000
    val combi_10000_5000 =
    for {
      c_10000 <- 0 to max_10000
      c_5000 <- 0 to N - c_10000
    } yield (c_10000, c_5000)

    @tailrec
    def rec(combi_10000_5000: List[(Int, Int)]): Option[(Int, Int, Int)] = combi_10000_5000 match {
      case Nil => None
      case head::tail => {
        val c_10000 = head._1
        val c_5000 = head._2
        val c_1000 = N - c_10000 - c_5000
        if (c_10000 * 10000 + c_5000 * 5000 + c_1000 * 1000 == Y) {
          Some(c_10000, c_5000, c_1000)
        } else {
          rec(tail)
        }
      }
    }

    rec(combi_10000_5000.toList) match {
      case Some((_1, _2, _3)) => println(_1 + " " + _2 + " " + _3)
      case None => println("-1 -1 -1")
    }
  }
}

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

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

int main(void)
{
    int n,m;
    cin>>n>>m;
    cout<<(n+m)*(n+m-1)/2-n*m<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>


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


const ll MOD=1000000007;


int main(void)
{
	char s[100000+2];
	vvll dp(4);
	char symbol[]="*ABC";


	while(scanf("%100000[ABC?]\n", s)==1)
	{
		int l=strlen(s);

		for(auto&mdp:dp) mdp.assign(l+1, 0);
		dp[0][0]=1;

		for(int i=0;i<=3;i++)
		{
			for(int j=0;j<l;j++)
			{
				dp[i][j+1]=dp[i][j]*((s[j]=='?')?3:1);
				if(s[j]==symbol[i])
				{
					dp[i][j+1]+=dp[i-1][j];
				}
				if(s[j]=='?')
				{
					if(i>0) dp[i][j+1]+=dp[i-1][j];
				}
				dp[i][j+1]%=MOD;
			}
		}
/*
		printf("  "); for(int i=0;i<l;i++) printf("%3c", s[i]); printf("\n");
		for(auto&mdp:dp)
		{
			for(auto&mmdp:mdp) printf("%2lld ", mmdp);
			printf("\n");
		}
*/
		printf("%lld\n", dp[3][l]);
	}

	return 0;
}


Measured memory_bytes: 3456
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <string>
#include <cstring>
using namespace std;

typedef long long ll;


int main(int argc, char const *argv[])
{
	ll x,y; cin>>x>>y;
	int ans=0;
	while(x<=y){
		x<<=1;
		ans++;
	}
	cout<< ans <<endl;
	return 0;
}

Measured memory_bytes: 256
import           Control.Applicative
import           Control.Monad
import           Data.List

main :: IO ()
main = do
  time:_ <- (map read . words) <$> getLine
  putStrLn $ show (hour time) ++ ":" ++ show (minute time) ++ ":" ++ show (second time)

hour :: Int -> Int
hour time = div time 3600

minute :: Int -> Int
minute time = mod (div time 60) 60

second :: Int -> Int
second time = mod time 60

Measured memory_bytes: 3600
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
	int A,B,C,D,sum1,sum2;
	cin>>A>>B>>C>>D;
	sum1=A+B;  sum2=C+D;
	if(sum1==sum2)      cout<<"Balanced"<<endl;
	else if(sum1>sum2) cout<<"Left"<<endl;
	else               cout<<"Right"<<endl;
	
	return 0;
}

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

int main() {
  
  int N, a, b, c;
  cin >> N;
  a = N % 2;
  b = ((N - a)/ 10) % 2;
  c = (N - a - 10 * b)/ 100;
  cout << a + b + c << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define br cout << "\n";
using namespace std;
const long long INF = 1e9;
const long long MOD = 1e9+7;
using Graph = vector<vector<ll>>;
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;}

// 0 false, 1 true 
// string to int : -48
// a to A : -32
// ceil(a)  1.2->2.0
// c++17	g++ -std=c++17 a.cpp

int main() {
    std::cout << std::fixed << std::setprecision(15);
    ll n, k;
    cin >> n >> k;
    string s; cin >> s;
    vector<long long> vec(n);
    for(long long i = 0; i < n; i ++){
        vec[i] = (ll)(s[i] - 48);
    }
    vector<ll> vec2;
    vector<ll> vec2_sum;
    vec2_sum.push_back(0);
    ll now = vec[0];
    ll count = 0;
    for(ll i = 0; i < n; i++){
        if(vec[i] == now){
            count++;
        }else{
            vec2.push_back(count);
            vec2_sum.push_back(vec2_sum[vec2_sum.size() - 1] + count);
            now = vec[i];
            count = 1;
        }
    }
    vec2.push_back(count);
    vec2_sum.push_back(vec2_sum[vec2_sum.size() - 1] + count);

    

    /*
    rep(i, vec2.size()){
        cout << vec2[i];
        (i == vec2.size() - 1) ? cout << endl : cout << " ";
    }
    cout << vec2.size() << endl;
    rep(i, vec2_sum.size()){
        cout << vec2_sum[i];
        (i == vec2_sum.size() - 1) ? cout << endl : cout << " ";
    }
    */
    

    ll ans = 0;
    
    if(vec[0] == 1){
        if(vec2.size() / 2 <= k){
            cout << n << endl;
            return 0;
        }
        ll seq = (k * 2) + 1;
        for(ll i = 0; i + seq < vec2_sum.size(); i+=2){
            ans = max(ans, vec2_sum[i + seq] - vec2_sum[i]);
        }
        if(vec[n-1] == 0 && vec2_sum.size() - 1 - (k*2) >= 0){
            ans = max(ans, vec2_sum[vec2_sum.size() - 1] - vec2_sum[vec2_sum.size() - 1 - (k*2)]);
        }
    }

    if(vec[0] == 0){
        if((vec2.size() + 1) / 2 <= k){
            cout << n << endl;
            return 0;
        }
        ll seq = (k * 2) + 1;
        for(ll i = 1; i + seq < vec2_sum.size(); i+=2){
            ans = max(ans, vec2_sum[i + seq] - vec2_sum[i]);
        }

        ans = max(ans, vec2_sum[k * 2] - vec2_sum[0]);
        if(vec[n-1] == 0 && vec2_sum.size() - 1 - (k*2) >= 0){
            ans = max(ans, vec2_sum[vec2_sum.size() - 1] - vec2_sum[vec2_sum.size() - 1 - (k*2)]);
        }
    }
    

    cout << ans << endl;

}

Measured memory_bytes: 2932
#include <stdio.h>

int main(void) {
    int len,i,j=0;
    char str1[101],str2[101],str3[202];
    
    scanf("%d",&len);
    scanf("%s %s",str1,str2);
    
    for (i=0;i<=len;i++) {
        str3[j]=str1[i];
        j++;
        str3[j]=str2[i];
        j++;
    }
    
    printf("%s\n",str3);
   
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> 
//#include <ext/pb_ds/tree_policy.hpp>
//#include <functional> // for less
//using namespace __gnu_pbds;
using namespace std;
typedef long long  L;

#define max_(x, y) (((x) > (y)) ? (x) : (y))
#define min_(x, y) (((x) < (y)) ? (x) : (y))
#define ___ ios_base::sync_with_stdio(false);cin.tie(NULL);
#define Mx 2000001
#define inf 1e15
const L MOD = 1e9+7;
const double pi = 2 * acos (0.0);

/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*---------------------------------------------------------------------*/


//typedef tree<L,null_type,less<L>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

L a1,a2,a3,b1,b2,b3,c,c1,c2,c3,d,d1,d2,d3,d4,d5,e1,e2,e3,f,h,k,l,m,n,m1,m2,n1,n2,o,p,p1,p2,p3,p4,
q,q1,q2,q3,q4,r,s,t,u,v,x,y,z,sum,mx=-inf,mn=inf,flg,flg1,flg2,id1,id2,id3,id4,lim;


int main()
{
    scanf("%lld%lld",&n,&m);
    printf("%lld\n", (n*(n-1))/2 + (m*(m-1))/2 ) ;
    return 0;
}
/// empty() lld I64d push_back() top() pop() insert() upper_bound() lower_bound() memset() max() min() scanf continue


Measured memory_bytes: 3828
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=3e5+10,mod=1e9+7;
inline void qr(int &x)
{
	x=0;char c=gc;int f=1;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
	while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
	x*=f;
}
void qw(int x)
{
	if(x<0)x=-x,putchar('-');
	if(x/10)qw(x/10);
	putchar(x%10+48);
}
struct edge{int y,next;}e[N<<1];int len,last[N];
void ins(int x,int y){e[++len]=(edge){y,last[x]};last[x]=len;}
int n,fa[N];
int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
int ring[N],tot,num[N],a[N];bool v[N];
bool fring(int x,int ed)
{
	if(x==ed){v[x]=1;ring[++tot]=x;return 1;}
	for(int k=last[x],y;k;k=e[k].next)
	{
		y=e[k].y;
		if(fring(y,ed)){v[x]=1;ring[++tot]=x;return 1;}
	}
	return 0;
}
int cnt,c[N],P[N],Q[N],sum[N];
void dfs(int x)
{
	int sz=0;
	for(int k=last[x],y;k;k=e[k].next)
	{
		y=e[k].y;
		if(!v[y])++sz,++cnt,dfs(y);
	}
	if(sz>1){puts("0");exit(0);}
}
int main()
{
	//freopen("dayinf.in","r",stdin);
	//freopen("dayinf.out","w",stdout);
	qr(n);
	for(int i=1;i<=n;i++)qr(a[i]),fa[i]=i;
	for(int i=1;i<=n;i++)
	{
		int p=get(i),q=get(a[i]);
		if(p!=q)fa[p]=q,P[q]|=P[p],Q[q]|=Q[p],ins(a[i],i);
		else P[q]=i,Q[q]=a[i];
	}
	int ans=1;
	for(int i=1;i<=n;i++)if(fa[i]==i)
	{
		tot=0;fring(P[i],Q[i]);
		for(int j=1;j<=tot;j++)cnt=0,dfs(ring[j]),num[j]=cnt;
		reverse(num+1,num+tot+1);
		int fi=-1,s1=1,s2=0,cal=0;
		for(int j=1;j<=tot;j++)if(num[j]){fi=j;break;}
		if(fi==-1){++sum[tot];continue;}
		if(tot==1)
		{
			if(num[fi]>1)return puts("0"),0;
			continue;
		}
		for(int j=tot+1;j<=3*tot;j++)num[j]=num[j-tot];
		for(int j=fi+1;j<fi+num[fi];j++)if(num[j])return puts("0"),0;
		for(int j=fi+num[fi],nxt=j+1;j<fi+tot;j=nxt,nxt=j+1)if(num[j])
		{
			if(j+num[j]-tot>fi){s1=0;return puts("0"),0;}
			for(;nxt<j+num[j];nxt++)if(num[nxt]){s1=0;return puts("0"),0;}
			if(num[j+num[j]])continue;
			s1=1ll*2*s1%mod;
		}
		cal=(cal+s1)%mod;
		if(!num[fi+num[fi]])
		{
			s2=1;
			for(int j=fi+num[fi]+1,nxt=j+1;j<fi+tot;j=nxt,nxt=j+1)if(num[j])
			{
				if(j+num[j]-tot>fi+1){s2=0;return puts("0"),0;}
				for(;nxt<j+num[j];nxt++)if(num[nxt]){s2=0;return puts("0"),0;}
				if(num[j+num[j]])continue;
				s2=1ll*2*s2%mod;
			}
		}
		cal=(cal+s2)%mod;
		ans=1ll*ans*cal%mod;
	}
	for(int i=1;i<=n;i++)if(sum[i])
	{
		if((i&1)&&i!=1)
		{
			c[0]=1;c[1]=2;
			for(int j=2;j<=sum[i];j++)
				c[j]=(c[j-1]*2+1ll*c[j-2]*(j-1)%mod*i%mod)%mod;
			ans=1ll*ans*c[sum[i]]%mod;continue;
		}
		c[0]=1;c[1]=1;
		for(int j=2;j<=sum[i];j++)
			c[j]=(c[j-1]+1ll*c[j-2]*(j-1)%mod*i%mod)%mod;
		ans=1ll*ans*c[sum[i]]%mod;
	}
	qw(ans);puts("");
	return 0;
}

Measured memory_bytes: 15488
import Control.Monad
import Data.Array
import qualified Data.ByteString.Char8 as C
import Data.Graph
import Data.List

main = sol <$> get >>= mapM_ put

get = fmap (unfoldr (C.readInt . C.dropWhile (==' '))) . C.lines <$> C.getContents 

put = putStrLn . show

sol ([n,m]:es) = fmap length $ elems g'
  where
  g = buildG (1,n) $ fmap (\[u,v] -> (u,v)) es
  g' = buildG (bounds g) (edges g ++ reverseE g)

reverseE = edges . transposeG

Measured memory_bytes: 508
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const double PI  = acos(-1.0);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;


void solve(){
	int n; cin>>n;
	VI P;
	rep(i,n){
		int p; cin>>p;
		P.PB(p);
	}
	VI Q = P;
	sort(ALL(Q));
	int cnt = 0;
	rep(i,n){
		if(P[i]!=Q[i]) cnt++;
	}
	if(cnt==0){
		cout << "YES" << endl;
	}else if(cnt==2){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
}

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}


Measured memory_bytes: 256
N=int(input())
W=list(map(int,input().split()))
maxi=sum(W)
mini=101
for i in range(N//2,N):
    num=sum(W[0:i])
    sa=maxi-num
    b=num-sa
    if mini>abs(b):
        mini=abs(b)
        aaa=i
for i in range(0,N//2)[::-1]:
    num=sum(W[0:i])
    sa=maxi-num
    b=num-sa
    if mini>abs(b):
        mini=abs(b)
        aaa=i
print(mini)

Measured memory_bytes: 3064
//Pranet Verma
#include <bits/stdc++.h>
using namespace std;
#define prev fdsf
#define next fsdfs
vector<int> g[100001];
int prev[100001], next[100001], vis[100001];
void expandRight(int u) {
	vis[u] = 1;
	for (auto v : g[u]) {
		if (!vis[v]) {
			next[u] = v;
			expandRight(v);
			break;
		}		
	}
}
void expandLeft(int u) {
	vis[u] = 1;
	for (auto v : g[u]) {
		if (!vis[v]) {
			prev[u] = v;
			expandLeft(v);
			break;
		}		
	}
}
vector<int> all;
void recoverRight(int u) {
	all.push_back(u);
	if (next[u]) {
		recoverRight(next[u]);
	}
}
void recoverLeft(int u) {
	if (prev[u]) {
		recoverLeft(prev[u]);
	}
	all.push_back(u);
}
int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	int left, right; 
	for (int i = 0; i < m; ++i) {
		int u, v;
		scanf("%d %d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
		left = u;
		right = v;
		if (u == v) {
			assert(false);
		}
	}
	vis[right] = 1;
	vis[left] = 1;
	expandRight(right);
	expandLeft(left);
	recoverLeft(left);
	recoverRight(right);
	printf("%d\n", (int)all.size());
	for (auto x : all) {
		printf("%d ", x);
	}
}

Measured memory_bytes: 10488
#include "bits/stdc++.h"
using namespace std;
#define Would
#define you
#define all(n)  n.begin(),n.end()
#define rall(n) n.rbegin(),n.rend()
typedef long long ll;
const ll INF = 2147483647;
const ll MOD = 1e9 + 7;
const double EPS = 1e-10;
const double pi = acos(-1);//3.1415926535897932384626433832795028...
const ll SIZE = 2000005;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 }, alp[30];
ll fac[SIZE], finv[SIZE], inv[SIZE];
vector<ll>dij;
struct edge { ll to, cost; };
vector<vector<edge> >G;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

ll mod_pow(ll a, ll b) {
	ll res = 1, mul = a;
	for (int i = 0; i < 31; ++i) {
		if (b >> i & 1) {
			res *= mul;
			res %= MOD;
		}
		mul = (mul * mul) % MOD;
	}
	return res;
}

void addedge(int from, int to, int cost) {
	G[from].push_back({ to,cost });
	G[to].push_back({ from,cost });
}

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T & t, const V & v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T & t, const V & v) {
	for (auto& e : t) fill_v(e, v);
}

template<typename T>
void outp(vector<T>v) {
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i];
		if (i != v.size() - 1) { cout << " "; }
	}
}

double add(double a, double b) {
	if (abs(a + b) < EPS * (abs(a) + abs(b))) { return 0; }
	return a + b;
}

double len(int a, int b, int c, int d) {
	return (double)sqrt((a - c) * (a - c) + (b - d) * (b - d));
}

struct ConvexHullTrick {
	//(slope,intercept)
	deque<pair<ll, ll> > dq;

	void add(ll a, ll b) {
		pair<ll, ll> p0 = make_pair(a, b);
		while (dq.size() >= 2) {
			ll sz = dq.size();
			std::pair<ll, ll> p1 = dq[sz - 1];
			std::pair<ll, ll> p2 = dq[sz - 2];
			if ((p0.second - p1.second) * (p0.first - p2.first) < (p0.second - p2.second) * (p0.first - p1.first)) { break; }
			dq.pop_back();
		}
		dq.push_back(p0);
	}

	ll query(ll x) {
		while (dq.size() >= 2) {
			ll v1 = dq[0].first * x + dq[0].second;
			ll v2 = dq[1].first * x + dq[1].second;
			if (v1 <= v2) { break; }
			dq.pop_front();
		}
		return dq[0].first * x + dq[0].second;
	}
};

ll a, b;
vector<ll>v, dp;
int main() {
	cin >> a >> b;
	v.resize(a), dp.resize(a);

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

	ConvexHullTrick cht;
	dp[0] = 0;
	cht.add(-2 * v[0], v[0] * v[0]);

	for (int i = 1; i < a; ++i) {
		dp[i] = cht.query(v[i]) + v[i] * v[i] + b;
		cht.add(-2 * v[i], v[i] * v[i] + dp[i]);
	}

	cout << dp[a - 1] << endl;
}

Measured memory_bytes: 5504
//=================================
// Created on: 2018/07/03 04:41:12
//=================================
#include <bits/stdc++.h>
using namespace std;
// 1 1 0 0 -1 -1
// 0 1 -1 1 0 1

int main()
{
    constexpr int dx[] = {1, 1, 0, 0, -1, -1};
    constexpr int dy[] = {0, 1, -1, 1, 0, -1};
    for (int T, N;;) {
        cin >> T >> N;
        if (T == 0 and N == 0) { break; }
        constexpr int S = 100;
        using P = pair<int, int>;
        vector<vector<bool>> used(2 * S + 1, vector<bool>(2 * S + 1, false));
        for (int i = 0, x, y; i < N; i++) { cin >> x >> y, used[y + S][x + S] = true; }
        queue<pair<P, int>> q;
        int sx, sy;
        cin >> sx >> sy;
        used[S + sy][S + sx] = true, q.push({{S + sy, S + sx}, 0});
        while (not q.empty()) {
            const int y = q.front().first.first, x = q.front().first.second, t = q.front().second;
            q.pop();
            if (t == T) { continue; }
            for (int i = 0; i < 6; i++) {
                const int newy = y + dy[i], newx = x + dx[i];
                if (used[newy][newx]) { continue; }
                used[newy][newx] = true, q.push({{newy, newx}, t + 1});
            }
        }
        int ans = -N;
        for (int i = -S; i <= S; i++) {
            for (int j = -S; j <= S; j++) {
                if (used[i + S][j + S]) { ans++; }
            }
        }
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 3084
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

MOD = 10 ** 9 +7

n,m = map(int,readline().split())
a = np.array(read().split(),np.int64)

a.sort()

def shake_cnt(x):
    X=np.searchsorted(a,x-a)
    return n*n-X.sum()

left = 0
right = 10 ** 6
while left+1 <right:
    x = (left + right)//2
    if shake_cnt(x) >= m:
        left = x
    else:
        right = x

left,right

X=np.searchsorted(a,right-a)
Acum = np.zeros(n+1,np.int64)
Acum[1:] = np.cumsum(a)

shake = n * n -X.sum()
happy = (Acum[-1]-Acum[X]).sum()+(a*(n-X)).sum()

happy += (m-shake)*left
print(happy)

Measured memory_bytes: 18240
#include <bits/stdc++.h>
// statics
using namespace std;
using int64 = int_fast64_t;
using PAIR = pair<int, int>;
constexpr int INF = 1 << 30;
constexpr int64 LINF = 1LL << 60;
constexpr int MOD = 1e9 + 7;
constexpr int MAX_N = 1e5 + 1;

// init/input
#define int int64
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...) type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T &t) {cin>>t;}
template<typename First, typename...Rest> void MACRO_VAR_Scan(First &first, Rest&...rest) {cin>>first;MACRO_VAR_Scan(rest...);}
#define VEC(type, c, n) vector<type> c(n);for(auto &&i:c)cin>>i;

// out
#define OUT(dist) cout<<(dist);
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define SP cout<<" ";
#define BR cout<<"\n";
#define debug(x) cerr<<#x<<":"<< (x);BR;

// utility
#define ALL(a) (a).begin(), (a).end()
#define EACH(i, a) for(auto &&i:(a))
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RFOR(i, a, b) for(int i=(b)-1;i>=0;--i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define RREP(i, n) for(int i=(n)-1;i>=0;--i)

signed main() {
  INIT;
	VAR(string, s);
	VAR(int, n);

	set< string > st;
	REP(i, s.size()) {
		FOR(j, 1, n + 1) {
			st.insert(s.substr(i, j));
		}
	}

	auto it = st.begin();
	REP(i, n - 1) {
		it++;
	}
	OUT(*it)BR;
  
  return 0;
}


Measured memory_bytes: 1664
#include <iostream>

using namespace std;

int cnt;
int A[500010], tmp[500010];

void margeSort(int l, int r) {
    if (r - l == 1) return;
    int m = (l + r) / 2;
    margeSort(l, m);
    margeSort(m, r);
    int i = 0;
    for (int il = l, ir = m; il < m || ir < r; cnt++)
        if (il < m)
            if (ir < r)
                tmp[i++] = A[il] < A[ir] ? A[il++] : A[ir++];
            else
                tmp[i++] = A[il++];
        else
            tmp[i++] = A[ir++];
    for (int j = 0; j < i; ++j) A[l + j] = tmp[j];
}

void outputArray(int a[], int n) {
    cout << a[0];
    for (int i = 1; i < n; ++i) {
        cout << ' ' << a[i];
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> A[i];
    margeSort(0, n);
    outputArray(A, n);
    cout << cnt << endl;
    return 0;
}



Measured memory_bytes: 6984
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,f[N],a[N];
int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
set<int>s[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),f[i]=i;
    while(m--)
    {
        int x,y;scanf("%d%d",&x,&y);
        f[getf(x)]=getf(y);
    }
    for(int i=1;i<=n;i++)
        s[getf(i)].insert(a[i]);
    int ans=0;
    for(int i=1;i<=n;i++)
        if(s[getf(i)].count(i)) ans++;
    printf("%d\n",ans);
}


Measured memory_bytes: 10368
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *
from fractions import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

A, B = map(int, input().split())
if B - A <= 10:
    print(reduce(lambda x, i: x ^ i, range(A, B + 1)))
    exit()
ans = 0
while A % 4 != 0:
    ans ^= A
    A += 1
while B % 4 != 3:
    ans ^= B
    B -= 1
print(ans)


Measured memory_bytes: 68332
#include <bits/stdc++.h>
using namespace std;
 
using ll=long long;
 
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
const int MOD = 1000000007; 


int main() {
    ll x; cin >> x;
    ll r = 100000, l = 0;
    while(l + 1 < r) {
        ll m = (l+r)/2;
        ll v = (m+1)*m/2;
        if (v >= x) r = m;
        else l = m;
    } 
    cout << r << endl; 
    return 0;
}

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

int main() {
	// your code goes here
	int N;
	cin >> N;

	vector<int> a(N);
	for(int i=0;i<N;i++) cin >> a[i];
	
	for(int i=0;i<N;i++){
		int target = a[i];
		for(int j=0; j<i; j++){
			if(target < a[j]){
				//target should be allocated to a[j]
				//previous a[j]~a[i-1] should be moved to right element
				for(int k=i-1; k>=j; k--){
					a[k+1] = a[k];
				}
				a[j] = target;
				break;
			}
		}
		
		//print intermediate sequence
		for(int n=0; n<N; n++){
			cout << a[n];
			if(n<N-1) cout << ' ';
			else cout << '\n';
		}
	}
	
	return 0;
}


Measured memory_bytes: 3136
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;

public class Main {

	public static void main(String[] args) {
		Task task = new Task();
		task.solve();
	}

	public static class Task {
		static final long MOD = (long) 1e9 + 7;

		public void solve() {
			Scan sc = new Scan();
			int n = (int) sc.scanLong();
			long cum = 0;
			long[] arr = new long[n];
			for (int i = 0; i < n; ++i) {
				long curr = sc.scanLong();
				cum += (curr) * (i % 2 == 0 ? 1 : -1);
				arr[i] = curr;
			}
			long[] res = new long[n];
			res[0] = cum;
			StringBuilder sb = new StringBuilder();
			sb.append(cum).append(' ');
			for (int i = 0; i < n-1; ++i) {
				long temp = arr[i] - res[i] / 2;
				res[i+1] = temp * 2;
				sb.append(res[i+1]).append(' ');
			}
			System.out.println(sb);
		}
	}

	public static class Scan {
		private byte[] buf = new byte[1024];
		private int index;
		private InputStream in;
		private int total;

		public Scan() {
			in = System.in;
		}

		public int scan() {
			if (total < 0)
				throw new InputMismatchException();
			if (index >= total) {
				index = 0;
				try {
					total = in.read(buf);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
				if (total <= 0)
					return -1;
			}
			return buf[index++];
		}

		public long scanLong() {
			long integer = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n)) {
				if (n >= '0' && n <= '9') {
					integer *= 10;
					integer += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			return neg * integer;
		}

		public double scanDouble() throws IOException {
			double doub = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n) && n != '.') {
				if (n >= '0' && n <= '9') {
					doub *= 10;
					doub += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			if (n == '.') {
				n = scan();
				double temp = 1;
				while (!isWhiteSpace(n)) {
					if (n >= '0' && n <= '9') {
						temp /= 10;
						doub += (n - '0') * temp;
						n = scan();
					} else
						throw new InputMismatchException();
				}
			}
			return doub * neg;
		}

		public String scanString() {
			StringBuilder sb = new StringBuilder();
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			while (!isWhiteSpace(n)) {
				sb.append((char) n);
				n = scan();
			}
			return sb.toString();
		}

		public char scanChar() {
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			return (char) n;
		}

		private boolean isWhiteSpace(int n) {
			if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1)
				return true;
			return false;
		}
	}
}


Measured memory_bytes: 40184
def main():
    n, y = map(int, input().split())
    res = {10000:0, 5000:0, 1000:0}
    if y % n == 0 and y//n in res:
        res[y//n] = n
        print(res[10000], res[5000], res[1000])
        return 0
    else:
        for i in range(0, y//10000+1):
            for j in range(0, y//5000+1):
                if 10000*i + 5000*j + 1000*max((n-i-j),0) == y and 0 <= n - (i+j):
                    res[10000] = i
                    res[5000] = j
                    res[1000] = n - i - j
                    print(res[10000], res[5000], res[1000])
                    return 0
        print(-1, -1, -1)

if __name__ == '__main__':
    main()

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

#pragma region Macros
using ll = long long;
#define int ll
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
template<class T = ll> using V = vector<T>;
template<class T = ll> using VV = V<V<T>>;
#define IOS\
    ios::sync_with_stdio(false);\
    cin.tie(0);\
    cout.tie(0);
#define FOR(i,l,r) for(ll i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(ll i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define SORT(name) sort(name.begin(), name.end())
#define RSORT(name)\
    SORT(name);\
    reverse(all(name));
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
inline void Yes(bool b = true) {cout << (b ? "Yes" : "No") << '\n';}
inline void YES(bool b = true) {cout << (b ? "YES" : "NO") << '\n';}
template <class T> inline void print(T x){ cout << x << '\n';}
template<typename T1,typename T2> inline void chmin(T1 &a, T2 b){ if(a > b) a = b; }
template<typename T1,typename T2> inline void chmax(T1 &a, T2 b){ if(a < b) a = b; }

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
#pragma endregion

#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const int MOD = 1000000007;
const int MAX_N = 100010;

signed main() {
    IOS;

    int N, M;
    cin >> N >> M;
    V<> A(N), B(M);
    REP(i, N) {
        cin >> A[i];
    }
    REP(i, M) {
        cin >> B[i];
    }
    auto res = convolution(A, B);
    for(int i = 0; i < (int)res.size(); ++i) {
        printf("%lld%c", res[i], (i != res.size() - 1) ? ' ' : '\n');
    }

    return 0;
}


Measured memory_bytes: 27300
input_num = int(input())
N = list(map(int,input().rstrip().split(" ")))
ans = True
for i in range(input_num):
  if N[i] % 2 == 0:
    if N[i] % 3 != 0 and N[i] % 5 != 0:
      ans = False
if ans:
  print("APPROVED")
else:
  print("DENIED")

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

int main(){
    int A, B, C, X;
    int ans = 0;
    cin >> A >> B >> C >> X;
    
    for(int i = 0; i <= A; i++){
        for(int j = 0; j <= B; j++){
            
            int nokori = X - (500 * i + 100 * j);
            int c_Cnt = nokori / 50;
            
            if(nokori >= 0 && C >= c_Cnt  && nokori % 50 == 0){
                ans++;
            }
        }
    }
    
    cout << ans << endl;
    
    
}


Measured memory_bytes: 3140
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define INF 2e9
#define LINF 1e18
#define mod 1e9+7
template<class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> P;


int main() {
    int n,m; cin >> n >> m;
    vector<int> p(m);
    vector<string> s(m);
    rep(i,m) cin >> p[i] >> s[i];
    rep(i,m) p[i]--;
    vector<int> wa(n);
    vector<bool> flag(n); //acしたらtrue
    rep(i,m) {
        if (flag[p[i]] == true) continue;
        if (s[i] == "AC") {
            flag[p[i]] = true;
        }
        else wa[p[i]]++;
    }
    int cntac = 0;
    int cntwa = 0;
    rep(i,n) {
        if (flag[i] == false) { //acできてないなら
            continue;
        }
        cntac++;
        cntwa += wa[i];
    }
    cout << cntac << " " << cntwa << endl;
}

Measured memory_bytes: 7004
#include <iostream>
#include <string>
#include <cstring>
using namespace std;

bool hi[20001];
bool lo[20001];

int main() {
    int n,t;
    string s;
    cin>>t;

    for(int i=0; i<t; ++i) {
        cin>>n;
        cin>>s;

        memset(hi, false, sizeof(hi));
        memset(lo, false, sizeof(lo));

        for(int i=0; i<2*n; ++i) {
            if(s[i] == 'Y') hi[(i+1)/2] = true;
        }
        for(int i=0; i<2*n; ++i) {
            if(s[i+2*n] == 'Y') lo[(i+1)/2] = true;
        }

        int ans = 0;
        int pos = 0;
        bool lh = false;
        for(int i=0; i<n+1; ++i) {
//            cout<<i<<" "<<hi[i]<<" "<<lo[i]<<" "<<pos<<" "<<ans<<endl;
            if(pos == 0) {
                if(lo[i]) {
                    ans += 2;
                    pos = 1;
                    lh = false;
                }else if(hi[i]) {
                    ans += 1;
                    pos = 1;
                    lh = true;
                }
            }else if(pos == 1) {
                if(lo[i] && hi[i]) {
                    lh = true;
                    ans += 2;
                }else if(lo[i] || hi[i]) {
                    lh = hi[i];
                    ans += 1;
                }
            }
            ans += 1;
        }

        if(pos == 0) ans -= 1;
        if(lh) ans -= 1;
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 1352