akhauriyash/Code-Regression huggingface dataset:
/* *
 *
 * Author: Hamkor
 *
 * */
 
#include <bits/stdc++.h>
 
using namespace std;
 
/* * * *   * * *   	* * * */
typedef long long ll;
const int oo = 1e9;
const ll mod = 100000000;
typedef complex<ll> P;
#define X real()
#define Y imag()
/* * * *   * * *   	* * * */
int l (int n, int w){return w%2? (n+1)%2 : n;}
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n; cin>>n;
	vector<vector<pair<int, int> > > a (n+1, vector<pair<int, int> >());
	vector<int> c (n+1, -1);
	for (int i=0; i<n-1; ++i){
		int u, v, w; cin>>u>>v>>w;
		a[u].push_back({v, w});
		a[v].push_back({u, w});
	}
	queue<int> q;
	c[1] = 0;
	q.push(1);
	while (!q.empty()){
		int s = q.front(); q.pop();
		for (auto i : a[s]){
			if (c[i.first] != - 1) continue;
			c[i.first] = l(c[s], i.second);
			q.push(i.first);
		}
	}
	for (int i=1; i<=n; ++i)printf("%d\n", c[i]);
	return 0;
}

Measured memory_bytes: 6784
using System;
using System.IO;

namespace AizuOnline
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var H = new int[1000];
            var W = new int[1000];
            var i = 0;

            while (true)
            {
                var x = Console.ReadLine().Split(' ');

                H[i] = Convert.ToInt32(x[0]);
                W[i] = Convert.ToInt32(x[1]);
                if (H[i] == 0)
                {
                    break;
                }
                i++;
            }

            for (int m = 0; m < H.Length && H[m] != 0; m++)
            {
                for (int k = 0; k < H[m]; k++)
                {
                    for (int j = 0; j < W[m]; j++)
                    {
                        if (k == 0 || k == H[m] - 1 || j == 0 || j == W[m] - 1)
                        {
                            Console.Write("#");
                        }
                        else
                        {
                            Console.Write(".");
                        }
                    }
                    Console.WriteLine();
                }
                Console.WriteLine();
            }

            Console.ReadLine();
        }
    }
}

Measured memory_bytes: 8940
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        boolean found  = false;
        for (int i = 0; i * 4 <= N; i++) {
            for (int j = 0; i* 4 + j * 7 <= N; j++) {
                if (i * 4 +  j * 7 == N) {
                    found = true;
                }
            }
        }
        System.out.println(found ? "Yes" : "No");
    }
}


Measured memory_bytes: 21972
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sidha(i,a,b) for(int i=a;i<b;i++)
#define vi vector<int> 
#define pb push_back
#define st string
#define pairi pair<int,int>

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
	string s;cin>>s;
	int c=count(s.begin(),s.end(),'R');
	if(c<=1 || c==3){
		cout<<c<<endl;
	}
	else{
		if(s[0]==s[1] || s[1]==s[2]){
			cout<<"2"<<endl;
		}
		else{
			cout<<"1"<<endl;
		}
	}
}

Measured memory_bytes: 3648
#include<iostream>
#include<cstdio>
using namespace std;
const long long md=1e9+7;
int n;
int a[100010];
long long p[100010];
int d;
long long po(long long x,long long pp)
{
	if(pp==1LL)return x;
	if(pp==0LL)return 1LL;
	long long res=po(x,pp>>1LL);
	res=res*res%md;
	if(pp&1LL)
	{
		res=res*x%md;
	}
	return res;
}
long long C(int x,int y)
{
	if(x==0 || x<y)return 0LL;
	if(y==0)return 1LL;
	long long s1=p[x],s2=p[x-y]*p[y]%md;
	return s1*po(s2,md-2LL)%md;
}
int main()
{
	scanf("%d",&n);
	p[0]=1LL;
	for(int i=1;i<=n+1;i++)
	{
		int x;
		scanf("%d",&x); 
		p[i]=p[i-1]*i%md;
		if(!a[x])a[x]=i;
		else
		{
			d=i-a[x]-1;
		}
	}
	for(int i=1;i<=n+1;i++)
	{
		if(i==1)printf("%d\n",n);
		else if(i==n+1)puts("1");
		else
		{
			printf("%lld\n",(C(n+1,i)-C(n-d-1,i-1)+md)%md);
		}
	}
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  for(int i=1; i<=9; i++) {
    for(int j=1; j<=9; j++) {
      if(i*j == N) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  cout << "No" << endl;
  return 0;
}



Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}

template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

const int inf = INT_MAX;
const int MOD = 1000000007;
const long long INF = LLONG_MAX;

// -------------------------------------------------------

int r, g, b;

int main() {
  cin >> r >> g >> b;
  int n = 100 * r + 10 * g + b;
  if (n % 4 == 0) {
    cout << "YES";
  } else {
    cout << "NO";
  }
}


Measured memory_bytes: 3648
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
using namespace std;
#define INF 110000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,int> P;

int dp[11000];

int main(){
  int a,b,h;
  cin>>a>>b>>h;
  cout<<(a+b)*h/2<<endl;
}


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

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define rep(i,n) for(int i=0; i<(int)(n); i++)
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; }

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

//constexpr ll mod = 998244353;
constexpr ll mod = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

vector<int> graph[200005];
vector<int> rev[200005];
int n;

bool check(int p, int k, vector<int>& a, vector<int>& c, queue<int>& q) {
  debug(p, k);
  a[p] = k;
  while(q.size()) {
    set<int> st;
    p = q.front(); q.pop();
    for(auto e: graph[p]) {
      debug(e, a[e]);
      st.insert(a[e]);
    }
    int now = 0;
    while(st.find(now) != st.end()) {
      now++;
    }
    a[p] = now;
    debug(p, a[p]);
    for(auto e: rev[p]) {
      c[e]--;
      if (c[e]==0) q.push(e);
    }
  }
  rep(i, n) {
    int now = 0;
    set<int> st;
    for(auto e: graph[i]) {
      st.insert(a[e]);
    }
    while(st.find(now) != st.end()) {
      now++;
    }
    if (now != a[i]) {
      return false;
    }
  }
  return true;
}

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

  cin >> n;

  vector<int> cnt(n);
  vector<int> ans(n, -1);

  rep(i, n) {
    int p; cin >> p; p--;
    graph[p].push_back(i);
    rev[i].push_back(p);
    cnt[p]++;
  }

  queue<int> que;
  rep(i, n) {
    if (cnt[i] == 0) {
      que.push(i);
    }
  }

  while(!que.empty()) {
    set<int> st;
    int p = que.front(); que.pop();
    for(auto e: graph[p]) {
      st.insert(ans[e]);
    }
    int now = 0;
    while(st.find(now) != st.end()) {
      now++;
    }
    ans[p] = now;
    debug(p, ans[p]);
    for(auto e: rev[p]) {
      cnt[e]--;
      if (cnt[e]==0) {
        que.push(e);
      }
    }
  }

  int p = -1;
  rep(i, n) {
    if (cnt[i] == 1) {
      p = i;
    }
  }
  if (p == -1) {
    cout << "POSSIBLE" << endl;
    return 0;
  }
  cnt[p] = 0;

  set<int> st2;
  for(auto e: graph[p]) {
    st2.insert(ans[e]);
  }
  int now = 0;
  while(st2.find(now) != st2.end()) {
    now++;
  }
  int a = now;
  now++;
  while(st2.find(now) != st2.end()) {
    now++;
  }
  int b = now;
  for(auto e: rev[p]) {
    cnt[e]--;
    if (cnt[e]==0) {
      que.push(e);
    }
  }

  vector<int> ans1 = ans;
  vector<int> cnt1 = cnt;
  queue<int> que1 = que;
  if (check(p, a, ans1, cnt1, que1) || check(p, b, ans, cnt, que)) {
    cout << "POSSIBLE" << endl;
  } else {
    cout << "IMPOSSIBLE" << endl;
  }
}

Measured memory_bytes: 24192
#include <bits/stdc++.h>
#include<iostream>
using namespace std;
 
int main() {
  int n,tmp;

  cin >> n;

  map<int,int> a;

  for(int i = 0;i < n;i++){
      cin >> tmp;
      a[tmp] = 1;
  }
  tmp = a.size();

  if(tmp == n){
     cout << "YES";
  }else{
      cout <<"NO";
  }
}
   


Measured memory_bytes: 9600
mod = 10**9 + 7
n = int(input())
l = list(map(int, input().split()))
 
d, ans = 0, 0
 
for i in range(1, n):
  f = 1 if i == 1 else f * (i-1) % mod
  d = (d * i + f) % mod
  ans = (ans * i + (l[i] - l[i-1]) * d) % mod
 
print(ans)

Measured memory_bytes: 15020
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define int long long
using namespace std;
inline int read(){
	int x=0,w=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return w?-x:x;
}
namespace star{
	const int maxn=1e5,mod=1e9+7;
	int h,w,a,b;
	inline int fpow(int a,int b){
		int ans=1;
		for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
		return ans;
	}
	int mul[maxn*2+10],inv[maxn*2+10];
	inline void pre(int n){
		mul[0]=inv[0]=1;
		for(int i=1;i<=n;i++)
			mul[i]=mul[i-1]*i%mod;
		inv[n]=fpow(mul[n],mod-2);
		for(int i=n-1;i;i--)
			inv[i]=inv[i+1]*(i+1)%mod;
	}	
	inline int C(int n,int m){
		return mul[n]*inv[n-m]%mod*inv[m]%mod;
	}
	inline void work(){
		h=read(),w=read(),a=read(),b=read();
		pre(h+w);
		int ans=0;
		for(int i=b+1;i<=w;i++)
			ans=(ans+C(h-a+i-2,i-1)*C(w+a-i-1,a-1)%mod)%mod;
		printf("%lld\n",ans);
	}
}
signed main(){
	star::work();
	return 0;
}

Measured memory_bytes: 6780
#include<bits/stdc++.h>
using namespace std;
using Graph=vector<vector<int>>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long 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;
}
int main(){
    ll N;cin>>N;
    vector<ll>A(N);
    rep(i,N){
        cin>>A[i];
    }
    set<ll>P;
    set<ll>R;
    set<ll>Q;
    rep(i,N){
        if(P.count(A[i])){
            Q.insert(A[i]);
        }
        P.insert(A[i]);
        R.insert(A[i]);
    }
    int count=0;
    for(auto value:P){
        if(Q.count(value)){
        }
        else{
            bool flag=true;
            for(ll i=1;i*i<=value;i++){
                bool flag2=true;
                if(value%i==0){
                    if(R.count(i)&&i!=value){
                        flag=false;
                        flag2=false;
                    }
                    if(R.count(value/i)&&i!=1){
                        flag=false;
                        flag2=false;
                    }
                }
                if(flag2=false){
                    break;
                }
            }
            if(flag){
                count++;
            }
        }
    }
    cout<<count<<endl;
}

Measured memory_bytes: 23372
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const int NINF = -1*INF;
const long long LLINF = 1ll << 60;
const long long LLNINF = -1*LLINF;

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vector<int>> vvi;
typedef vector<vll> vvll;
typedef vector<vd> vvd;
typedef vector<vld> vvld;
 
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define revAll(x) x.rbegin(), x.rend()
#define gcd(a, b) __gcd(a, b)
#define popcount(x) __builtin_popcount(x)
#define isize(x) (int)(x.size())
#define rep(i,n) for(int i = 0; i < n; i++)
#define umap unordered_map
#define uset unordered_set
#define pq priority_queue

const ll MOD = 1e9 + 7;

void madd(ll& a, ll b){
	a += b;
	if (a >= MOD) a -= MOD;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	int n; cin >> n;
	auto dp = vector<vvll>(n+1, vvll(2, vll(2, 0)));	
	dp[0][0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int has0 = 0; has0 <= 1; has0++) {
			for (int has9 = 0; has9 <= 1; has9++) {
				for (int d = 0; d <= 9; d++) {
					int n0 = (d == 0 or has0) ? 1 : 0;
					int n9 = (d == 9 or has9) ? 1 : 0;
					madd(dp[i+1][n0][n9], dp[i][has0][has9]);
				}
			}
		}
	}
	cout << dp[n][1][1];
}

Measured memory_bytes: 151380
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <complex>

#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,n) for(int i=0;i<(n); i++)

using namespace std;
typedef long long ll;
const int MAX_N = 100;
const int MAX_W = 1000000000;
static const int INF = 1<<29;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(0); //この2行はより速度を向上させる
    // 追加２, 以降 cin の入力元が 'input.txt' になる
    //提出時に消す！！
 

    int N,A,B;
    cin >> N >> A >> B;

    int a=N*A;
    int ans=min(a,B);
    cout << ans << endl;

    return 0;

}

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

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];

    int ret = 0;
    vector<bool> dp(1 << n);
    for (int bit = 0; bit < 1 << n; bit++) {
        int nowCount = 0, nowSum = 0;
        bool canMake = false;
        for (int i = 0; i < n; i++) {
            if (bit & (1 << i)) {
                nowCount++, nowSum += a[i];
                if (dp[bit ^ (1 << i)])canMake = true;
            }
        }
        if (canMake || nowSum == k) dp[bit] = true;
        else ret = max(ret, nowCount);
    }

    cout << n - ret << endl;
    return 0;
}


Measured memory_bytes: 3236
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = "";  
        String text;
        String Lower_text;
        int count = 0;
        int textlen;
        int i=0;
        String testtext;        
        while(true){
            try{
                text = sc.next();
                Lower_text = text.toLowerCase();
                str = str + Lower_text;
            }catch(Exception e){
                break;
            }        
            i++;
            /*textlen = text.length();
            testtext = text.substring(textlen-1);
            if(testtext.equals(".")) break;*///Judging wether text contains "." or not            
        }
        char[] c = str.toCharArray();
        int[] alphabet;
        alphabet = new int[26];
        
        for(count=0;count<str.length();count++){
            if((c[count]-'a')>= 0 && (c[count]-'a')<=25){
                alphabet[(c[count]-'a')]++;
                //System.out.println(c[count]);
            }            
        }
        for(count=0;count<26;count++){
            System.out.println((char)(count+'a') + " : " + alphabet[count]);
        }
        sc.close();
    }
}


Measured memory_bytes: 26884
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rrep(i,n) for (int i = n-1; i >= 0; i--)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,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;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    int ans = 0;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    int sum = 0;
    rep(i,n) sum += a[i];
    rep(i,n) {
        if(a[i]*4*m >= sum) ans++;
    }
    cout << (ans >= m ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
//#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
void _main()
{
    int N, Q;
    cin >> N >> Q;
    vector<tuple<int, int, int>> a(N);
    rep(i, 0, N)
    {
        int S, T, X;
        cin >> S >> T >> X;
        a[i] = make_tuple(X, S - X, T - X);
    }
    sort(a.begin(), a.end());

    set<pair<int, int>> qs;
    rep(i, 0, Q)
    {
        int D;
        cin >> D;
        qs.insert(make_pair(D, i));
    }

    const int INF = 1000000005;
    vector<int> ans(Q, INF);

    for (const auto& t : a)
    {
        int X, S, T;
        tie(X, S, T) = t;

        auto itS = qs.lower_bound(make_pair(S, 0));
        auto itT = qs.lower_bound(make_pair(T, 0));

        if (itS == qs.end()) continue;
        if (itT == qs.begin()) continue;

        auto itS2 = itS;

        while ((itS != qs.end()) && ((itT == qs.end()) || (*itS < *itT)))
        {
            chmin(ans[itS->second], X);
            ++itS;
        }

        qs.erase(itS2, itT);
    }

    rep(i, 0, Q)
    {
        cout << ((ans[i] != INF) ? ans[i] : -1) << endl;
    }
}


Measured memory_bytes: 15744
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, m;
char s[N];
int f[N], w[3];
bool st[N];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < 3; i ++)  scanf("%d", &w[i]);
    scanf("%s", s + 1);
    
    for(int i = 1; i <= n; i ++)
    {
        if(s[i] == 'r')  s[i] = 0;
        else if(s[i] == 's')  s[i] = 1;
        else if(s[i] == 'p')  s[i] = 2;     //  s[i] - 1可以赢s[i]
        
        if(i - m >= 1 and s[i] == s[i - m] and st[i - m])  f[i] = f[i - 1];
        else  f[i] = f[i - 1] + w[(s[i] - 1 + 3) % 3],  st[i] = true;
    }
    printf("%d", f[n]);
    return 0;
}

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

int n;
vector<vector<int>> g;
vector<int> dp;

int solve();
int dfs(int now, int par);
int reroot(int now, int par);

int main() {
  cin >> n;
  g.resize(n);
  for (int i = 1; i < n; ++i) {
    int a, b;
    cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  cout << solve() << endl;
  return 0;
}

int solve() {
  dp.assign(n, 0);
  dfs(0, -1);
  return reroot(0, -1) + 1;
}

int dfs(int now, int par) {
  int res = 0, len;
  vector<int> v;
  for (auto to : g[now])
    if (to != par) v.push_back(dfs(to, now));
  len = v.size();
  sort(v.begin(), v.end());
  if (len >= 2)
    for (int i = 1; i < len; ++i) v[i] = max(v[i], 1);
  for (auto p : v) res += p;
  return dp[now] = res;
}

int reroot(int now, int par) {
  int res = 0, len = g[now].size(), sum = 0, bf = dp[now];
  vector<int> id;
  for (int i = 0; i < len; ++i) id.push_back(g[now][i]);
  sort(id.begin(), id.end(), [](int l, int r) { return dp[l] < dp[r]; });
  for (int i = 0; i < len; ++i) res += max(dp[id[i]], (int)(i != 0));
  sum = res;
  if (len == 2) sum = dp[id[0]] + dp[id[1]];
  for (int i = 0; i < len; ++i) {
    int to = id[i];
    if (to == par) continue;
    if (len == 1)
      dp[now] = 0;
    else if (len == 2)
      dp[now] = sum - dp[to];
    else {
      if (i == 0)
        dp[now] = sum - max(dp[id[1]], 1) + dp[id[1]] - dp[to];
      else
        dp[now] = sum - dp[to];
    }
    res = min(res, reroot(to, now));
  }
  dp[now] = bf;
  return res;
}


Measured memory_bytes: 24480
#include <bits/stdc++.h>
        using namespace std;
        #define int long long
const int MAX = 200001;
const int MOD = 1000000007;
  
        signed main() {
        int n,m,k;
        cin>>n>>m>>k;
        vector<int> g[n];
        int a,b;
        for(int i=0;i<m;i++){
                cin>>a>>b;a--;b--;
                g[a].push_back(b);
                g[b].push_back(a);
        }
      
int ans[n]={};
        int ban[n]={},x=0,y;
        bool used[n]={};
        queue<int> que,que2;
        for(int i=0;i<n;i++){
                if(used[i])continue;
                x++;
                que.push(i);
                while(!que.empty()){
                        if(used[que.front()]){
                                que.pop();
                                continue;
                        }
                        used[que.front()]=true;
                        ban[que.front()]=x;
                        for(int j=0;j<g[que.front()].size();j++)if(!used[g[que.front()][j]]){
                                que.push(g[que.front()][j]);
                        }
                        que2.push(que.front());
                        que.pop();
                }
                y=que2.size();
                while(!que2.empty()){
                        ans[que2.front()]=y-1;
                        que2.pop();
                }

        }
        for(int i=0;i<k;i++){
                cin>>a>>b;a--;b--;
                if(ban[a]==ban[b]){
                        ans[a]--;ans[b]--;
                }
        }
        for(int i=0;i<n;i++)cout<<ans[i]-g[i].size()<<' ';

      }


        


Measured memory_bytes: 9588
#include<iostream>
using namespace std;
int main () {

  int t,n,a[100],max,max2;

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

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

    max=a[1]-a[0];
    max2=a[0]-a[1];
    
    for(int j=0 ; j < n-1 ; j++){
      if( a[j+1]-a[j] > max ){
	max=a[j+1]-a[j];
      }
      if( a[j]-a[j+1] > max2){
	max2=a[j]-a[j+1];
      }
    }

    if(max2 < 0){
      max2=0;
    }
    if(max < 0){
      max=0;
    }
	

    cout <<max<<" "<<max2<<endl;

  }

  return 0;

}

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

public class AtCoderC
{
    static void Main()
    {
        string s = Console.ReadLine();
        while (s.Length > 0)
        {
            if (s.StartsWith("dream"))
            {
                s = s.Substring(5);
                if (s.StartsWith("er") && !s.StartsWith("era"))
                {
                    s = s.Substring(2);
                }
            }
            else if (s.StartsWith("erase"))
            {
                s = s.Substring(5);
                if (s.StartsWith("r"))
                {
                    s = s.Substring(1);
                }
            }
            else
            {
                Console.WriteLine("NO");
                return;
            }
        }
        Console.WriteLine("YES");
    }
}

Measured memory_bytes: 34620
# -*- coding: utf-8 -*-
line = input().split()
n = int(line[0])
m = int(line[1])

path = [[] for _ in range(n)]
for _ in range(m):
    line = input().split()
    a = int(line[0])-1
    b = int(line[1])-1
    path[a].append(b)

def dfs(i, s):
    if i==n-1:
        if s==2:
            return True
        else:
            return False

    for e in path[i]:
        if dfs(e, s+1):
            return True
    return False

if dfs(0,0):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")


Measured memory_bytes: 29068
a, b, n = gets.chomp.split(" ").map(&:to_i);

max = 0
x = 0
while (x < n) do
  if ((a*(x+10000000000))/b)-a*((x+10000000000)/b) >= max && x + 10000000000 < n
    max = [((a*(x+10000000000))/b)-a*((x+10000000000)/b), max].max
    x += 10000000000
  elsif ((a*(x+1000000000))/b)-a*((x+1000000000)/b) >= max && x + 1000000000 < n
    max = [((a*(x+1000000000))/b)-a*((x+1000000000)/b), max].max
    x += 1000000000
  elsif ((a*(x+100000000))/b)-a*((x+100000000)/b) >= max && x + 100000000 < n
    max = [((a*(x+100000000))/b)-a*((x+100000000)/b), max].max
    x += 100000000
  elsif ((a*(x+1000000))/b)-a*((x+1000000)/b) >= max && x + 1000000 < n
    max = [((a*(x+1000000))/b)-a*((x+1000000)/b), max].max
    x += 1000000
  elsif ((a*(x+10000))/b)-a*((x+10000)/b) >= max && x + 10000 < n
    max = [((a*(x+10000))/b)-a*((x+10000)/b), max].max
    x += 10000
  elsif ((a*(x+100))/b)-a*((x+100)/b) >= max && x + 100 < n
    max = [((a*(x+100))/b)-a*((x+100)/b), max].max
    x += 100
  elsif ((a*(x+10))/b)-a*((x+10)/b) >= max && x + 10 < n
    max = [((a*(x+10))/b)-a*((x+10)/b), max].max
    x += 10
  elsif ((a*(x+1))/b)-a*((x+1)/b) >= max 
    max = [((a*(x+1))/b)-a*((x+1)/b), max].max
    x += 1
  else
    break 
  end
end

puts max

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

int main(){
  int H, W;
  cin >> H >> W;
  char a[H][W];
  vector<int> hb(H);
  vector<int> wb(W);
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      cin >> a[i][j];
      if(a[i][j]=='#'){
        hb.at(i)++;
        wb.at(j)++;
      }
    }
  }
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      if(hb.at(i)>0 && wb.at(j)>0) cout << a[i][j];
    }
    if(hb.at(i)>0) cout << endl;
  }
}

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

int main(){
    char x, y;  // ??\?????????????????????
    char comma; // cin??????????????????????????????????????????????????°
    char ball_position = 'A';       // ??????????????????

    while(cin >> x >> comma >> y){
        if (x == ball_position) {
            ball_position = y;
        }else if (y == ball_position) {
            ball_position = x;
        }
    }
    cout << ball_position << endl;
    return 0;
}

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

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

using namespace std;
using lint=long long;

int main(){
	lint n,a,b,c,d; cin>>n>>a>>b>>c>>d;
	n--;
	rep(i,n+1) if(i*c-(n-i)*d<=b-a && b-a<=i*d-(n-i)*c) return puts("YES"),0;
	puts("NO");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long int 
#define f(i,n) for(int i=0;i<(n);i++)
#define rep(i,a,n) for(int i=(a);i<=(n);i++)
#define vi vector<int>
#define pi pair<int,int>
#define pb push_back
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define inf LONG_MAX
#define ninf LONG_MIN
const int mod = 1e9+7;

int32_t main() {
  ios_base::sync_with_stdio(false);cin.tie(NULL);
  
  int n,m;
  cin>>n>>m;
  vi g[n];
  int ans[n];
  f(i,n)
  ans[i]=-1;
  ans[0]=0;
  f(i,m){
    int a,b;
    cin>>a>>b;
    a--;b--;
    g[a].pb(b);
    g[b].pb(a);
  }
  queue<int> q;
  q.push(0);
  while(!q.empty()){
    int a=q.front();
    q.pop();
    for(auto i:g[a])
      if(ans[i]==-1){
        ans[i]=a;
        //vis[i]=1;
        q.push(i);
      }
  }
  bool ok=1;
  f(i,n)
  if(ans[i]==-1)
    ok=0;
  if(ok){
    cout<<"Yes\n";
    f(i,n)
    if(i)
      cout<<ans[i]+1<<"\n";

  }
  else
    cout<<"No\n";
  
  return 0;
}

Measured memory_bytes: 12940
#include <bits/stdc++.h>
using namespace std;
typedef long long lol;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(lol i=0;i<lol(n);i++)
#define REPD(i,n) for(lol i=n-1;i>=0;i--)
#define FOR(i,a,b) for(lol i=a;i<=lol(b);i++)
#define FORD(i,a,b) for(lol i=a;i>=lol(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() //sortなどの引数を省略したい
#define SIZE(x) lol(x.size()) //sizeをsize_tからllに直しておく
//定数
#define PI 3.1415926535897932385 //pi
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//最大値最小値
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main()
{
    lol result{0};
    lol n; cin >> n;
    //lol k; cin >> k;
    vector<string> a(n);
    REP(i, n)
    {
        cin >> a[i];
    }
    sort(ALL(a));
    string save = "aaaaaaaaaaa";
    REP(i, n)
    {
        if(save == a[i])
        {

        }
        else
        {
            result++;
            save = a[i];
        }
        
    }
    

    cout << result << endl;
    return 0;
}

Measured memory_bytes: 9596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll inf=1000000007;
const ll maxinput=100005;
const ll mod=998244353;
#define mp make_pair
int n,k,a[105];
int ways(int pos,int remain)
{
    if(pos==n)
    {
        if(remain==0)
            return(1);
        else
            return(0);
    }
    int temp=0;
    for(int i=0;i<=a[pos];i++)
    {
        if(i<=remain)
            temp+=ways(pos+1,remain-i); //temp=ways(pos+1,remain)+....+temp(pos+1,remain-a[pos])
        else
            break;
    }
    return(temp);
}
int dp[105][100005];//dp[i][j] is the the number of ways to distribute j candies among student i,i+1...n-1 respecting constraints
void bottomup()
{
    dp[n][0]=1;
    for(int j=1;j<maxinput;j++)
        dp[n][j]=0;

    //taking prefix sum
    for(int j=1;j<maxinput;j++)
        dp[n][j]+=dp[n][j-1];

    for(int i=n-1;i>=0;i--)
    {
        for(int j=0;j<maxinput;j++)
        {
           // dp[i][j]=dp[i+1][j]-((j>=a[i])?0:dp[i+1][j-a[i]-1]);
            if(j<=a[i])
                dp[i][j]=dp[i+1][j]%inf;
            else
                dp[i][j]=(dp[i+1][j]-dp[i+1][j-a[i]-1])%inf;
        }
        //taking prefix sum
        for(int j=1;j<maxinput;j++)
            dp[i][j]+=dp[i][j-1],dp[i][j]%=inf;
    }
}
int main()
{   
    cin>>n>>k;
    for(int i=0;i<n;i++)
        cin>>a[i];
    bottomup();
    //cout<<ways(0,k)<<endl;
    if(k==0)
        cout<<1<<endl;
    else
        cout<<(dp[0][k]-dp[0][k-1]+inf)%inf<<"\n";
}

Measured memory_bytes: 41216
#include <stdio.h>
#include <math.h>

int main(){
  int a, b, C;
  double c, PI, rad, S, L, h;
  PI = acos(-1);

  scanf("%d %d %d", &a, &b, &C);

  rad = C * PI / 180;
  S = a*b*sin(rad)/2;
  c = sqrt( a*a+b*b-2*a*b*cos(rad) );
  L = a + b + c;
  h = 2*S/a;

  printf("%lf\n", S);
  printf("%lf\n", L);
  printf("%lf\n", h);

}

Measured memory_bytes: 2092
#include <cstdio>
#include <algorithm>

using i32 = int;
using i64 = long long;
constexpr i32 maxn = 20000;

inline i32 in() {
	i32 n;
	scanf("%d", &n);
	return n;
}

i32 p[maxn + 1],
	a[maxn + 1],
	b[maxn + 1];
i32 main() {
	const i32 n = in();
	for (i32 i = 1; i <= n; ++i)
		a[i] = 30000 * i, b[n + 1 - i] = a[i];
	for (i32 i = 1; i <= n; ++i)
		p[i] = in(), a[p[i]] += i;

		
	for (i32 i = 1; i <= n; ++i)
		printf("%d%c", a[i], " \n"[i == n]);
	for (i32 i = 1; i <= n; ++i)
		printf("%d%c", b[i], " \n"[i == n]);
	
	return 0;
}

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

int main() {
  string s;
  cin>>s;
  if(s=="SUN"){
    cout<<"7"<<endl;
  }
  else if(s=="MON"){
    cout<<"6"<<endl;
  }
  else if(s=="TUE"){
    cout<<"5"<<endl;
  }
  else if(s=="WED"){
    cout<<"4"<<endl;
  }
  else if(s=="THU"){
    cout<<"3"<<endl;
  }
  else if(s=="FRI"){
    cout<<"2"<<endl;
  }
  else if(s=="SAT"){
    cout<<"1"<<endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define div1 1000000007
const long long INF = 1LL << 60;
using namespace std;
typedef long long ll;
typedef long double ld;
// a>b -> a==b;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
// a<b -> a==b;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main(void)
{
    ll N, K, i, ans=0;

    cin >> N >> K;

    for(i=K; i<=N+1; i++){
        ans += ((N+1)-i)*i+1;
        ans %= div1;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3676
using System;

namespace abc063_b
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = Console.ReadLine();
            bool[] find = new bool[150];
            bool ret = true;
            for (int i = 0; i < s.Length; i++)
            {
                if (find[s[i]]) { ret = false; }
                else
                {
                    find[s[i]] = true;
                }
            }
            Console.WriteLine(ret ? "yes" : "no");
        }
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

void solve(){
    int n;
    cin >> n;
    string s,t;
    cin >> s;
    t=s;
    reverse(all(t));
    vi ctr(n,0);
    vi seen(26,0);
    rp(i,n){
        if(seen[s[i]-'a']==0){
            ctr[i]++;
            seen[s[i]-'a']=1;
        }
    }
    fill(all(seen),0);
    rp(i,n){
        if(seen[t[i]-'a']==0){
            ctr[n-1-i]--;
            seen[t[i]-'a']=1;
        }
    }
    int ans=0;
    int sum=0;
    rp(i,n){
        sum+=ctr[i];
        chmax(ans,sum);
    }
    print(ans);
    return;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    solve();
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define ll long long
#define ull unsigned long long
#define M 1000000007
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define RFOR(i,m,n) for(int i=m;i>=n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265


void f(){
  string s;
  cin>>s;
  map<string,bool> mp;
  rep(i,s.size()){
    string t,u;
    rep(j,i){
      t += s[j];
    }
    FOR(j,i,s.size()){
      u += s[j];
    }
    mp[t+u] = true;
    mp[u+t] = true;
    reverse(all(t));
    mp[t+u] = true;
    mp[u+t] = true;
    reverse(all(u));
    mp[t+u] = true;
    mp[u+t] = true;
    reverse(all(t));
    mp[t+u] = true;
    mp[u+t] = true;
  }
  cout<<mp.size()<<endl;
}


int main(){
  int n;
  cin>>n;
  rep(i,n){
    f();
  }

  return 0;
}


Measured memory_bytes: 3260
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define ll long long
#define ld long double
#define inf 1000000000
using namespace std;
#define N 205
#define mod 998244353
int n,pw[N],ans;
struct node{ int x,y; }a[N];
int main(){
	scanf("%d",&n);
	pw[0]=1; rep (i,1,n) pw[i]=2ll*pw[i-1]%mod;
	ans=(pw[n]+mod-1-n)%mod;
	rep (i,1,n) scanf("%d%d",&a[i].x,&a[i].y);
	rep (i,1,n) rep (j,i+1,n){
		int sum=0;
		rep (k,j+1,n)
			if ((a[i].y-a[j].y)*(a[j].x-a[k].x)==(a[i].x-a[j].x)*(a[j].y-a[k].y)) sum++;
		ans=(ans+mod-pw[sum])%mod;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 384
#include <stdio.h>

int main()
{
	int n, k, x, y;
	
	scanf("%d %d %d %d", &n, &k, &x, &y);
	
	if(n <= k) printf("%d", x*n);
	else printf("%d", k*x + (n-k)*y);
	
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  
  bool flag=false;
  if(n%2!=0){
    vector<int> v(n);
    v.at(0) = 7%n;
    for(int i=1; i<n; i++)
      v.at(i) = (v.at(i-1)*10 + 7) % n;
    
    for(int i=0; i<n; i++)
      if(v.at(i)==0){
        cout << i+1 << endl;
        flag=true;
        break;
      }
  }
  if(!flag)
    cout << "-1" << endl;
}


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

using namespace std;
using Int = long long;

signed main(){
    Int n;
    cin >> n;
    vector<Int> d;
    for(Int i = 0; i < n; i++){
        Int tmp;
        cin >> tmp;
        d.push_back(tmp);
    }
    sort(d.begin(), d.end());

    cout << d[n/2] - d[n/2 - 1] << endl;

    return 0;
}

Measured memory_bytes: 1400
n = int(input())
b = list(map(int, input().split()))
a = []
count = 0

for _ in range(n):
    for i in reversed(range(len(b))):
        if b[i] == i+1:
            a.append(b.pop(i))
            count += 1
            break

if count != n:
    print(-1)
else:
    for ai in a[::-1]:
        print(ai)

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

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  int planA = N * A;
  int planB = B;
  if (planA > planB) {
    cout << planB << endl;
  }
  else {
    cout << planA << endl;
  }
}

Measured memory_bytes: 3536
def run():
  N, K = map(int, input().split())
  ps = list(map(int, input().split()))
  dp = [0]*(N-K+1)
  ans = 0
  dp[0] = sum(ps[0:K])
  for n in range(1, N-K+1):
    dp[n] = dp[n-1]+ps[n+K-1]-ps[n-1]
  print((max(dp)+K)/2)

if __name__ == '__main__':
    run()

Measured memory_bytes: 25060
/*
 ________  ___   ___  ________
|\   __  \|\  \ |\  \|\   __  \
\ \  \_\ /\ \  \\_\  \ \  \|\  \
 \ \   __\_\ \______  \ \  \\\  \
  \ \  \_\  \|_____|\  \ \  \\\  \
   \ \______/|     \ \__\ \_______\
    \|______|/      \|__|\|_______|

*/
#include<bits/stdc++.h>

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

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

#define all(x) x.begin(),x.end()
#define pb push_back
#define lowbit(x) x&-x
#define lc rt<<1
#define rc rt<<1|1
#define ls lc,l,m
#define rs rc,m+1,r

#define dbg(x) cout<<' '<<#x<<" = "<<x<<endl;
#define dbg2(x,y) {cout<<' '<<#x<<" = "<<x<<',';dbg(y)}
#define dbg3(x,y,z) {cout<<' '<<#x<<" = "<<x<<',';dbg2(y,z)}

int read(int &x){return scanf("%d",&x);}
int read(ll &x){return scanf("%lld",&x);}
int read(double &x){return scanf("%lf",&x);}

int read(int &x,int &y){return scanf("%d%d",&x,&y);}
int read(ll &x,ll &y){return scanf("%lld%lld",&x,&y);}
int read(double &x,double &y){return scanf("%lf%lf",&x,&y);}

int read(int &x,int &y,int &z){return scanf("%d%d%d",&x,&y,&z);}
int read(ll &x,ll &y,ll &z){return scanf("%lld%lld%lld",&x,&y,&z);}
int read(double &x,double &y,double &z){return scanf("%lf%lf%lf",&x,&y,&z);}

ll qpow(ll a,ll b,ll mod){if(a==0)return 0;ll ans=1;a%=mod;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans%mod;}
ll inv(ll x,ll mod){return qpow(x,mod-2,mod);}


int dir[4][2]={0,1,0,-1,1,0,-1,0};
int mon[13]={ 0,31,28,31,30,31,30,31,31,30,31,30,31};

const int INF =0x3f3f3f3f;
const int mod = 1e9+7;
const int N = 5e5+5;

struct DSU{
	int f[N];
	void init(int n){fe(i,0,n)f[i] = i;}//remember initial
	int fa(int x){return f[x]==x?x:f[x]=fa(f[x]);}
	void join(int x,int y){x=fa(x);y=fa(y);if(x!=y)f[x]=y;}
};
struct CombMath{
	int C[2005][2005];
    void init(int n){
		fe(i,1,n)
			fe(j,1,n)
                C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;
    }
};

char s[N];
ll a[N];

signed main(){
//	freopen("in1.txt","r",stdin);
//	freopen("in2.txt","r",stdin);
//	freopen("in3.txt","r",stdin);
//	freopen("in4.txt","r",stdin);
//	freopen("in5.txt","r",stdin);
//	freopen("BZW.txt","r",stdin);


	int n;
	read(n);
	fe(i,1,n)read(a[i]);
	sort(a+1,a+1+n,greater<int>());

	ll tot = 0;
    fe(i,1,n){
        int l = i+1,r = n;
        while(l<r){
			if(a[l]+a[r]>a[i]){
				tot+=r-l;
				l++;
			}else r--;
        }
    }
	printf("%lld\n",tot);



    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int F[10000] = { 0 };

int fn(int n) {
	if (n == 0 || n == 1) return F[n]=1;
	if (F[n] != 0)return F[n];
	return F[n] = fn(n - 1) + fn(n - 2);
}

int main()
{
	int n;
	scanf("%d", &n);
	printf("%d\n", fn(n));
	return 0;
}

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

const int inf = 1e9;
const ll linf = 1e18;

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

    int m; cin >> m;
    cout << 48 - m << endl;
    return 0;
}

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

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

	int ans = 0;

	for (int b = 2; b * b <= x ; b++){
		
		int tmp = 1;
	
		while (true) {

			tmp *= b;

			if (x < tmp) {
				tmp /= b;
				break;
			}
			
		}

		ans = max(ans, tmp);
	}
		
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double

using namespace std;
ll n, t, sum, mx, mn, m, k, a[200001];

void solve(){
	cin >> n >> k;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a, a + n);
	for(int i = 0; i < n - k; i++)
	{
		sum += a[i];
	}
	cout << sum;
}

int main()
{
	t = 1;
//	cin >> t;
	while(t--){
		solve();
	}
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include<bitset>
using  namespace std;
#define ll long long
#define pb push_back
#define sc second
#define fr first
#define mp make_pair
const int N = 3e5 + 10, Max = 2e5 + 10;
const ll  MOD = 1e9 + 7, OO = 1e9;
int main() {
	int a, b;
	cin >> a >> b;
	int diff = abs(b - a);
	if (diff % 2 == 1)
		return cout << "IMPOSSIBLE" << endl, 0;
	cout << max(b, a) - diff / 2 << endl;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <vector>
#include <algorithm>

#define int64 long long int
using namespace std;

int main()
{
	int n, c, buf, len;
	char str[1024]={0};
	cin >> n;

	if((c = getchar()) == '\n')
	for(int i=0; i<n; i++){
		buf = 0;
		while(1){
			c = getchar();
			if(c == '\n' || c == EOF){
				str[buf] = '\0';
				break;
			}
			str[buf] = c;
			buf++;
		}
		len = strlen(str);
		for(int j=0; j<=len-7; j++){
			if(str[j] != 'H') continue;
			if(str[j+1] != 'o') continue;
			if(str[j+2] != 's') continue;
			if(str[j+3] != 'h') continue;
			if(str[j+4] != 'i') continue;
			if(str[j+5] != 'n') continue;
			if(str[j+6] != 'o') continue;
			str[j+6] = 'a';
		}
		printf("%s\n", str);
		memset(str, 0, 1024);
	}

	return 0;
}

Measured memory_bytes: 1124
#include <stdio.h>
int main()
{
    int n;
    int i;
    int sum=0;
    char s[60];
    if(scanf ("%d",&n)==1)
    {
        scanf("%s",s);
        for(i=0;i<n-2;i++)
        {
            if(s[i]=='A' && s[i+1]=='B' && s[i+2]=='C')
            {
                sum++;
                i+=2;
            }
        }
        printf("%d",sum);
    }
    return 0;
}


Measured memory_bytes: 128
n = int(input())
a = list(map(int, input().split()))
bit = [[0,0] for i in range(60)]
b = []
ans = 0
mod = 10 ** 9 + 7
for i in a:
  for j in range(60):
    bit[j][i % 2] += 1
    i //= 2
for k,(z,o) in enumerate(bit):
  ans = (ans + (z * o) * (pow(2,k,mod))) % mod
print(ans)

Measured memory_bytes: 122808
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <bitset>


typedef long long ll;
#define fi first
#define se second
const ll mod = 1000000007;
//              123456789

using namespace std;

///////////////////////////////////////////////
//
//
///////////////////////////////////////////////

////////////////////////////////////////////////
////////////////////////////////////////////////

int N;
string S;

int cnt = 0;
int s = 0;


int main(){
  
  int i;
  
  cin>>N;
  cin>>S;
  
  for( i = 0; i < N; i++ ){
    if( S[i] == '(' ) cnt++;
    if( S[i] == ')' ){
      if( cnt > 0 ){
        cnt--;
      }
      else{
        s++;
      }
    }
  }
  
  for( i = 0; i < s; i++ ){
    printf("(");
  }
  
  cout<<S;
  
  for( i = 0; i < cnt; i++ ){
    printf(")");
  }
  
  puts("");
  

  
  return 0;
}

Measured memory_bytes: 256
import sys
n,x = list(map(int, input().split()))
l = list(map(int, input().split()))
isum = 0
for i in range(1,n+1):
    isum += l[i-1]
    if isum > x:
        print(i)
        sys.exit()
print(n+1 if sum(l) <= x else i)

Measured memory_bytes: 3060
N, C = gets.split.map(&:to_i)
ds = []
C.times do |i|
    ds[i] = gets.split.map(&:to_i)
end
cs = []
N.times do |i|
    cs[i] = gets.split.map(&:to_i)
end

result = Array.new(3){Array.new(C, 0)}

C.times do |c|
    N.times do |i|
        N.times do |j|
            result[(i+j)%3][c] += ds[cs[i][j]-1][c]
        end
    end
end

ans = 10**20

C.times do |c1|
    C.times do |c2|
        next if c1 == c2
        C.times do |c3|
            next if c3 == c1 || c3 == c2
            res = result[0][c1] + result[1][c2] + result[2][c3]
            ans = res if ans > res
        end
    end
end
puts ans

Measured memory_bytes: 6396
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#define ll long long
using namespace std;
ll gcd(int a,int b);


int main(){
  int n,m;
  scanf ("%d %d",&n,&m);
  string s,t;
  cin >> s >> t;
  ll g=gcd(s.size(),t.size());
  ll sa=s.size()/g;
  ll ta=t.size()/g;
  ll i;
  for(i=0;i<g;i++){
    if(s[sa*i]!=t[ta*i]) break;
  }
  if(i==g){
    cout << g*sa*ta << endl;
  }
  else{
    cout << "-1" << endl;
  }
}


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


Measured memory_bytes: 512
n=int(input())
s=input()
from collections import Counter
c=Counter(s)
t=c['R']*c['G']*c['B']
for i in range(n):
  for j in range(i+1, min(n, (n+1+i)>>1)):
    k = 2*j - i
    if k < n and s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
      t-=1
print(t)

Measured memory_bytes: 68896