akhauriyash/Code-Regression huggingface dataset:
/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

#include <bits/stdc++.h>
using namespace std;

#define DEBUG
#ifndef DEBUG
#define endl "\n"
#define log(args...)
#else
#define log(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); logf(_it, args); }
void logf(istream_iterator<string> it) {
}
template<typename T, typename ... Args>
void logf(istream_iterator<string> it, T a, Args ... args) {
	cout << *it << " = " << a << endl;
	logf(++it, args...);
}
#endif

#define forn(i,k,n) for(ll i=(k); i<(n); i++)

const double PI = acos(-1);
typedef long long ll;
#define fori(n) for(ll i=0; i<(n); i++)

#define cins(s) string s; cin>>s;
#define cini(i) int i; cin>>i;
#define cinll(l) ll l; cin>>l;
#define cind(d) double d; cin>>d;
#define cinai(a, n) vi a(n); fori(n) { cin>>a[i]; }
#define cinall(a, n) vll a(n); fori(n) { cin>>a[i]; }
#define cinas(s, n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a, n) vd a(n); fori(n) { cin>>a[i]; }

typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<string> vs;
typedef vector<ll> vll;

void solve() {
	cini(n);
	cini(R);
	int ans = R;
	if (n < 10)
		ans = R + (100 * (10 - n));

	cout << ans << endl;
}

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



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

struct Heap{
	vector<int> Array;
	
	int pai(int input){
		return (input - 1)/2;
	}
	
	int filhoEsquerdo(int input){
		return (2*input + 1);
	}
	
	int filhoDireito(int input){
		return (2*input + 2);
	}
	
	// Arruma após inserção
	void HeapifyRemover(int arrumar){
		int esquerdo = filhoEsquerdo(arrumar);
		int direito = filhoDireito(arrumar);
		
		int maior = arrumar;
		
		//Vejo quem é maior
		if (esquerdo < Array.size() && Array[esquerdo] > Array[arrumar]){
			maior = esquerdo;
		}
		if (direito < Array.size() && Array[direito] > Array[maior]){
			maior = direito;
		}
		if (maior != arrumar){
			swap(Array[arrumar], Array[maior]);
			HeapifyRemover(maior);
		}
	}
	
	void HeapifyInserir(int arrumar){
		if (arrumar && Array[pai(arrumar)] < Array[arrumar]){
			swap(Array[pai(arrumar)], Array[arrumar]);
			HeapifyInserir(pai(arrumar));
		}
	}
	
	void inserirHeap(int valor){
		Array.push_back(valor);
		HeapifyInserir(Array.size() - 1);
	}
	
	void printaRaiz(){
		printf("%i\n", Array.at(0));
	}
	
	int removerRaiz(){
		Array[0] = Array.back();
		Array.pop_back();
		HeapifyRemover(0);
	}
};

int main(){
	Heap heap;
	string operacao; int valor;
	while(cin >> operacao){
		if (operacao == "insert"){
			cin >> valor;
			heap.inserirHeap(valor);
		} else if (operacao == "extract"){
			heap.printaRaiz();
			heap.removerRaiz();
		} else {
			break;
		}
	}
	return 0;
}



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

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

int main() {
  int64_t x;
  cin >> x;
  cout << x / 11 * 2 + (x % 11 > 0 ? x % 11 > 6 ? 2 : 1 : 0) << endl;
}



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

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const long long INF = 1LL << 60;

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define fr(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;//繰り返し二乗法
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll kaijo(ll x){
  ll z=1;
  if(x==0){
    return 1;
  }
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll yakusu_num(ll n){
  vl yakusu(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      yakusu[i]++;
    }
  }
  if(n!=1)yakusu[n]++;
  ll num=1;
  for(ll i=0;i <=n;i++){
    num*=yakusu[i];
  }
  return num;
}


//cout<<""<<endl;
int main(){
  int N,X,T;cin>>N>>X>>T;
  cout<<((N+X-1)/X)*T<<endl;
}





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

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
#define MOD 1000000007

using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int iy[]={0, 0, 1, -1};
int ix[]={1, -1, 0, 0};

int n, m, k, bl[2001][2001], wh[2001][2001], b[2001][2001], w[2001][2001], x[100001], y[100001];
char c[100001];

int main(){
	int ans=0;
	cin >> n >> k;
	int whc=0;
	int blc=0;
	for(int i=0;i<n;i++){
		cin >> x[i] >> y[i] >> c[i];
		int xi ,yi;
		xi = (x[i]%(2*k)?x[i]%(2*k) : 2*k);
		yi = (y[i]%(2*k)?y[i]%(2*k) : 2*k);
		if(c[i]=='B'){
			b[xi][yi]++;
			blc++;
		}
		if(c[i]=='W'){
			w[xi][yi]++;
			whc++;
		}
	}
	for(int i=1;i<=2*k;i++){
		for(int j=1;j<=2*k;j++){
			wh[i][j] = wh[i-1][j]+wh[i][j-1]-wh[i-1][j-1]+w[i][j];
			bl[i][j] = bl[i-1][j]+bl[i][j-1]-bl[i-1][j-1]+b[i][j];
		}
	}
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			int sum = 0;
			sum = bl[2*k][2*k]-bl[i+k-1][2*k]-bl[2*k][j+k-1]+(2*bl[i+k-1][j+k-1])+bl[i-1][2*k]+bl[2*k][j-1]-2*(bl[i+k-1][j-1]+bl[i-1][j+k-1])+2*bl[i-1][j-1];
			sum += whc - (wh[2*k][2*k]-wh[i+k-1][2*k]-wh[2*k][j+k-1]+2*wh[i+k-1][j+k-1]+wh[i-1][2*k]+wh[2*k][j-1]-2*(wh[i+k-1][j-1]+wh[i-1][j+k-1])+2*wh[i-1][j-1]);	
			ans = max(max(ans,sum),n-sum);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 63616
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    int a,b;
    cin >> a >> b;
    if(a %3 == 0 || b % 3 == 0 || (a+b) %3 == 0)cout << "Possible" << endl;
    else cout << "Impossible" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 200005
#define mod 1000000007
using namespace std;
template<typename T>
inline void in(T &x)
{
	x=0;
	char c=getchar();
	bool fu=0;
	while(c<'0'||c>'9'){if(c=='-')fu=1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
int n,a[N],sum[N],ans;
int main()
{
	in(n);
	for(int i=0;i<n;++i)in(a[i]);
	sum[n-1]=a[n-1];
	for(int i=n-2;i>=0;--i)sum[i]=(a[i]+sum[i+1])%mod;
	for(int i=0;i<n-1;++i)ans=(ans+(1LL*a[i]*sum[i+1]%mod))%mod;
	printf("%d\n",ans);
	return 0;
}

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


int main() {
    ll n;
    cin >> n;
    string ans = "No";
    while (n > 0){
        if (n%10 == 7) ans = "Yes";
        n /= 10;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3544
#include<iostream>

using namespace std;

int solve(int& n){
  if(n==1) return 0;
  int m=1;
  for(int i=2; i*i<n; ++i){
    if(!(n%i)){
      m+=i;
      if(i!=n/i) m+=n/i;
    }
  }
  return m;
}

int main(){
  int n, m;
  while(cin >> n && n){
    m = solve(n);
    if(n==m) cout << "perfect number" << endl;
    else if(n<m) cout << "abundant number" << endl;
    else cout << "deficient number" << endl;
  }
  return 0;
}

Measured memory_bytes: 1156
#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
int mp[1002][1002],mp2[1002][1002];
int main()
{
	char a;
	int t, j, h, w, k, i;
	pair<int, int> s, m[10];
	queue<pair<int, int> > u;
	queue<int> e;
	cin >> h >> w >> k;
	for (i = 0; i <= h; i++)
	{
		mp[i][0] = 1;
		mp[i][w + 1] = 1;
		mp2[i][0] = 1;
		mp2[i][w + 1] = 1;

	}
	for (i = 0; i <= w; i++)
	{
		mp[0][i] = 1;
		mp[h + 1][i] = 1;
		mp2[0][i] = 1;
		mp2[h + 1][i] = 1;
	}
	for (i = 1; i <= h; i++)
	{
		for (j = 1; j <= w; j++)
		{
			cin >> a;
			if (a == 'X')
			{
				mp[i][j] = 1;
			}
			if (a == 'S')
			{
				mp[i][j] = 10;
				s.first = i;
				s.second = j;
			}
			if (a == '1')
			{
				mp[i][j] = 11;
				m[1].first = i;
				m[1].second = j;
			}
			if (a == '2')
			{
				mp[i][j] = 12;
				m[2].first = i;
				m[2].second = j;
			}
			if (a == '3')
			{
				mp[i][j] = 13;
				m[3].first = i;
				m[3].second = j;
			}
			if (a == '4')
			{
				mp[i][j] = 14;
				m[4].first = i;
				m[4].second = j;
			}
			if (a == '5')
			{
				mp[i][j] = 15;
				m[5].first = i;
				m[5].second = j;
			}
			if (a == '6')
			{
				mp[i][j] = 16;
				m[6].first = i;
				m[6].second = j;
			}
			if (a == '7')
			{
				mp[i][j] = 17;
				m[7].first = i;
				m[7].second = j;
			}
			if (a == '8')
			{
				mp[i][j] = 18;
				m[8].first = i;
				m[8].second = j;
			}
			if (a == '9')
			{
				mp[i][j] = 19;
				m[9].first = i;
				m[9].second = j;
			}
		}
	}
	t = 0;
	e.push(0);
	i = 1;
	u.push(s);
	while (i <= k)
	{
		t = e.front();
		e.pop();
		s = u.front();
		u.pop();
		if (s == m[i])
		{
			i++;
			memset(mp2, 0, sizeof(mp2));
			while (!u.empty())
			{
				u.pop();
			}
			while (!e.empty())
			{
				e.pop();
			}
			e.push(t);
			u.push(s);
			continue;
		}
		if (mp[s.first + 1][s.second] != 1 && mp2[s.first + 1][s.second] != 1)
		{
			mp2[s.first + 1][s.second] = 1;
			s.first++;
			u.push(s);
			t++;
			e.push(t);
			t--;
			s.first--;
		}
		if (mp[s.first][s.second + 1] != 1 && mp2[s.first][s.second + 1] != 1)
		{
			mp2[s.first][s.second + 1] = 1;
			s.second++;
			u.push(s);
			t++;
			e.push(t);
			t--;
			s.second--;
		}
		if (mp[s.first - 1][s.second] != 1 && mp2[s.first - 1][s.second] != 1)
		{
			mp2[s.first - 1][s.second] = 1;
			s.first--;
			u.push(s);
			t++;
			e.push(t);
			t--;
			s.first++;
		}
		if (mp[s.first][s.second - 1] != 1 && mp2[s.first][s.second - 1] != 1)
		{
			mp2[s.first][s.second - 1] = 1;
			s.second--;
			u.push(s);
			t++;
			e.push(t);
			t--;
			s.second++;
		}
	}
	cout << t << endl;
	return 0;
}

Measured memory_bytes: 11016
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException{
        FastReader in = new FastReader();
        FastWriter out = new FastWriter();
        int n = in.nextInt();
        Integer[] a = new Integer[n];
        int sum = 0;
        for (int i = 0; i < n; i++){
            a[i] = in.nextInt();
            sum += a[i];
        }
        int prevSum = 0, ans = 0;
        int already = (int) 1e9;
        for (int i = 0; i < n-1; i++){
            prevSum += a[i];
            already = Math.min(already, Math.abs(prevSum - (sum-prevSum)));
        }
        out.pl(already);
        out.close();
    }
}
class FastReader{ 
    BufferedReader br; 
    StringTokenizer st; 
    public FastReader() { 
        br = new BufferedReader(new InputStreamReader(System.in)); 
    } 
    String next(){ 
        while (st == null || !st.hasMoreElements()) { 
            try{ 
                st = new StringTokenizer(br.readLine()); 
            }catch (IOException  e){ 
                e.printStackTrace(); 
            } 
        } 
        return st.nextToken(); 
    } 
    int nextInt(){ 
        return Integer.parseInt(next()); 
    } 
    long nextLong(){ 
        return Long.parseLong(next()); 
    } 
    double nextDouble(){ 
      return Double.parseDouble(next()); 
    } 
    String nextLine(){ 
        String str = ""; 
        try{ 
            str = br.readLine(); 
        } 
        catch (IOException e){ 
            e.printStackTrace(); 
        } 
        return str; 
    } 
}
class FastWriter{
    PrintWriter out;
    FastWriter(){
        out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	out.flush();
    }
    void pl(Object o){
        out.write(o.toString());
	    out.write("\n");
        out.flush();
    }
    void pl(){
        out.write("\n");
    }
    void p(Object o){
        out.write(o.toString());
    }
    void close(){
        out.flush();
        out.close();
    }  
}


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

using namespace std;

void solve()
{
    string s;
    cin >> s;
    int n = s.size();
    bool f = 1;
    for (int i = 0; i < n; i++)
    {
        if (i & 1)
        {
            f &= (s[i] == 'L' || s[i] == 'U' || s[i] == 'D');
        }
        else
        {
            f &= (s[i] == 'R' || s[i] == 'U' || s[i] == 'D');
        }
    }
    cout << (f ? "Yes" : "No") << endl;
}

int main()
{
    solve();
    return 0;
}


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

using namespace std;
#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define _dec(i,N,j) for(int i = (N-1);i >= (j);i--)
#define _rec(i,N,j) for(int i = (N);i >=(j);i--)
#define ALL(x) x.begin(),x.end()
#define MEM(a,n) memset(a,n,sizeof(a))
#define fst first
#define scd second
#define PB push_back
#define MP make_pair

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

int get_int(){int x;scanf("%d",&x);return x;}
LL get_ll(){LL x;scanf("%lld",&x);return x;}
double get_db(){double x;scanf("%lf",&x);return x;}

template<typename T> int chmin(T &a,T b){if(a > b){a = b;return 1;}else return 0;}
template<typename T> int chmax(T &a,T b){if(a < b){a = b;return 1;}else return 0;}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {_for(i,0,v.size()) os << v[i] << " ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){for(auto a:v) os << a <<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& v){os << v.fst <<" "<<v.scd << " ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>& v){for(auto a:v) cout << a << endl;return os;}

static const int dx[8] = { -1,  0, 1, 0,  1, -1,  1, -1};
static const int dy[8] = {0,  1, 0,  -1,  1, -1, -1,  1};
const double pi  = acos(-1.0);
const double eps = 1e-8;
//const LL  INF  = 0x3f3f3f3f3f3f3f3f;
const int inf  = 0x3f3f3f3f;

const int maxn = 1e5+5;


int A,B,C;
int main()
{   
    cin >> A >> B >> C;
    if(A + B + C >= 22) cout << "bust" << endl;
    else cout << "win" << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#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,n) for(int i = 1; i <= (n); ++i)
#define rrep2(i,n) for(int i = (n); i > 0; --i)
#define srep(i,s,n) for(int i = s; i < (n); ++i)
#define rsrep(i,s,n) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<(x)<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { int n = (__VA_ARGS__).size(); rep(i, n) printf("%d%s", (__VA_ARGS__)[i], i != n-1 ? " " : "\n"); }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;


int main() {
    int n;
    cin >> n;
    vint a(n);
    rep(i, n) cin >> a[i];

    rep(i, n) {
        if (a[i]&1) continue;
        if (a[i]%3 == 0 || a[i]%5 == 0) continue;
        puts("DENIED");
        return 0;
    }
    puts("APPROVED");
    return 0;
}

Measured memory_bytes: 256
fn main() {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).ok();
    let s: Vec<u32> = buf
        .trim()
        .chars()
        .map(|c| c.to_digit(10).unwrap())
        .collect();
    let mut ans_first_zero = 0;
    let mut ans_first_one = 0;
    for i in 0..s.len() {
        if i % 2 == s[i] as usize {
            ans_first_zero += 1;
        } else {
            ans_first_one += 1;
        }
    }
    println!("{}", std::cmp::min(ans_first_zero, ans_first_one));
}


Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>

#define endl '\n'
#define ll long long

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int k, a, b;
	cin >> k >> a >> b;

	int curr = k;
	while (curr <= b)
	{
		if (curr >= a && curr <= b) {
			cout << "OK" << endl;
			return 0;
		}
		curr += k;
	}
	cout << "NG" << endl;
	return 0;
}

Measured memory_bytes: 3440
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

using namespace std;

int main(){
	
	while(true){
		string str;
		cin >> str;
		if(str[0] == '0'){
			break;
		}
		map<string, int> m;
		
		queue<string> que;
		que.push(str);
		
		for(int loop = 0; loop < 10000000; loop++){
			int N = que.size();
			if(N == 0){
				break;
			}
			for(int poyo = 0; poyo < N; poyo++){
				string s = que.front();
				//cout << s << endl;
				que.pop();
				if(m.find(s) != m.end()){
					continue;
				}
				m[s] = loop;
				for(int i = 0; i < s.size() - 1; i++){
					string ss = s;
					if(s[i] != s[i + 1]){
						if(s[i] != 'r' && s[i + 1] != 'r'){
							ss[i] = 'r';
							ss[i + 1] = 'r';
						}else if(s[i] != 'b' && s[i + 1] != 'b'){
							ss[i] = 'b';
							ss[i + 1] = 'b';
						}else{
							ss[i] = 'g';
							ss[i + 1] = 'g';
						}
					}
					que.push(ss);
				}
			}
		}
		int ans = 10000000;
		for(int i = 0; i < str.size(); i++){
			str[i] = 'r';
		}
		if(m.find(str) != m.end()){
			ans = min(ans, m[str]);
		}
		for(int i = 0; i < str.size(); i++){
			str[i] = 'b';
		}
		if(m.find(str) != m.end()){
			ans = min(ans, m[str]);
		}
		for(int i = 0; i < str.size(); i++){
			str[i] = 'g';
		}
		if(m.find(str) != m.end()){
			ans = min(ans, m[str]);
		}
		if(ans == 10000000){
			cout << "NA" << endl;
		}else{
			cout << ans << endl;
		}
	}
	
	return 0;
}

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

using namespace std;

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

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int h, w;
    bool exist = false;
    cin >> h >> w;
    vector<int> cnt(26, 0);
    rep (i, h) rep (j, w) {
        char c;
        cin >> c;
        cnt[c - 'a']++;
    }
    vector<int> mod(4);
    rep (i, 26) mod[cnt[i] % 4]++;
    if (h % 2 && w % 2) {
        if (mod[1] != 1 || mod[3] || (cnt[2] > (h - 1) / 2 + (w - 1) / 2)) cout << "No" << endl;
        else cout << "Yes" << endl;
    } else if (!(h % 2) && !(w % 2)) {
        if (mod[1] || mod[2] || mod[3]) cout << "No" << endl;
        else cout << "Yes" << endl;
    } else {
        if (w % 2) swap(h, w);
        if ((mod[1] || mod[3]) || (mod[2] > w / 2)) cout << "No" << endl;
        else cout << "Yes" << endl; 
    }

    return 0;
}



Measured memory_bytes: 384
#define alphanso                  \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL)
#include <bits/stdc++.h>
using namespace std;
int main()
{
	alphanso;
	int n, i, flag = 0;
	cin >> n;
	vector<int> v(n), s(n);
	for (auto &it : v)
		cin >> it;
	s = v;
	sort(s.begin(), s.end());
	for (i = 0; i < v.size(); i++)
	{
		if (v[i] != s[i])
			flag++;
	}
	flag <= 2 ? cout << "YES" : cout << "NO";
	return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define all(v) (v).begin(),(v).end()
typedef long long int ll;
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4


int main(){
  int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;

  int x3, y3, x4, y4, a;
  x3 = x2 - y2 + y1;
  y3 = y2 + x2 - x1;
  x4 = x1 - y2 + y1;
  y4 = y1 + x2 - x1;

  cout << x3 << " " << y3 << " " <<  x4 <<  " " << y4 << endl;

  return 0;
}

Measured memory_bytes: 256
def main():
    import os
    import sys
    from io import BytesIO, IOBase
    
    BUFSIZE = 8192
    
    
    class FastIO(IOBase):
        newlines = 0
    
        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = "x" in file.mode or "r" not in file.mode
            self.write = self.buffer.write if self.writable else None
    
        def read(self):
            while True:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines = 0
            return self.buffer.read()
    
        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b"\n") + (not b)
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines -= 1
            return self.buffer.readline()
    
        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                self.buffer.truncate(0), self.buffer.seek(0)
    
    
    class IOWrapper(IOBase):
        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode("ascii"))
            self.read = lambda: self.buffer.read().decode("ascii")
            self.readline = lambda: self.buffer.readline().decode("ascii")
    
    
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

    n = int(input())
    a = [int(x) for x in input().split()]

    from collections import defaultdict

    dp = defaultdict(lambda : -float('inf'))
    dp[(0, 0, 0)] = 0

    for i in range(1, n + 1):
        max_j = i//2 if i % 2 == 0 else i//2 + 1
        min_j = n//2 - (n - i)//2 if (n - i) % 2 == 0 else n//2 - ((n - i)//2 + 1)
        for j in range(min_j, max_j + 1):
            dp[(i, j, 0)] = max(dp[(i - 1, j, 0)], dp[(i - 1, j, 1)])
            dp[(i, j, 1)] = dp[(i - 1, j - 1, 0)] + a[i - 1]
    print(max(dp[(n, n//2, 0)], dp[(n, n//2, 1)]))
main()




Measured memory_bytes: 303640
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const double EPS = 1e-7;
const int INF = INT_MAX;
const ll LLINF = INT64_MAX;
const double PI = acos(-1);
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

const string SINF = "-";
int match[] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};

void chmax(string &a, string b)
{
    if (a == SINF)
    {
        a = b;
    }
    else if (a.size() < b.size())
    {
        a = b;
    }
    else if (a.size() == b.size())
    {
        if (a < b)
        {
            a = b;
        }
    }
}

string dp[11000];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    for (int i = 0; i < m; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < 11000; i++)
    {
        dp[i] = SINF;
    }
    dp[0] = "";
    for (int i = 0; i <= n; i++)
    {
        if (dp[i] == SINF)
        {
            continue;
        }
        for (auto num : a)
        {
            chmax(dp[i + match[num]], dp[i] + (char)('0' + num));
        }
    }
    cout << dp[n] << endl;
}

Measured memory_bytes: 43776
import java.util.*;
import java.io.*;
import java.math.*;
 
 
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
 
public class Main{
    static final long mod=1000000007;
    
    public  static void main(String[] args)   throws Exception, IOException{
        Reader sc = new Reader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        // int n=sc.nextInt();
        // char c[][] = new char[h][w];
        // char c[]=sc.nextString().toCharArray();
        // for(int i=0; i<n; i++) {a[i]=sc.nextInt();}
        int n=sc.nextInt();
        int a[] =new int[n];
        for(int i=0; i<n; i++) {a[i]=sc.nextInt()-i-1;}
        sort(a);
        int b=a[n/2];
        long ans=0;
        for(int i=0; i<n; i++) {
            ans+=abs(a[i]-b);
        }

        out.println(ans);
        out.flush();
    }

    static void db(Object... os){
        System.err.println(Arrays.deepToString(os));
    }
     
    static boolean validpos(int x,int y,int r, int c){
        return x<r && 0<=x && y<c && 0<=y;
    }
    
    static boolean bit(long x,int k){
        // weather k-th bit (from right) be one or zero
        return  ( 0 < ( (x>>k) & 1 )  )  ? true:false;
    }    

    class P implements Comparable<P>{
        long x;
        double d;
        P(long x, double d) {
            this.x=x;
            this.d=d;
        } 
          
        public int compareTo(P p){
            return (d - p.d)>0?1:-1;//des
        } 
    }
}
class Reader
{ 
    private BufferedReader x;
    private StringTokenizer st;
    
    public Reader(InputStream in)
    {
        x = new BufferedReader(new InputStreamReader(in));
        st = null;
    }
    public String nextString() throws IOException
    {
        while( st==null || !st.hasMoreTokens() )
            st = new StringTokenizer(x.readLine());
        return st.nextToken();
    }
    public int nextInt() throws IOException
    {
        return Integer.parseInt(nextString());
    }
    public long nextLong() throws IOException
    {
        return Long.parseLong(nextString());
    }
    public double nextDouble() throws IOException
    {
        return Double.parseDouble(nextString());
    }
}

Measured memory_bytes: 46492
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		int a = 100000;
		int n = stdIn.nextInt();
		for (int i = 0; i < n; i++) {
			a *= 1.05;
			if(a%1000!=0){a+=1000-a%1000;}
		}
		System.out.println(a);
	}
}

Measured memory_bytes: 17136
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <climits>
#include <bitset>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define MAX 100000

vector<bool> is_prime(100001, true);

void get_prime(){
	is_prime[0]=false;
	is_prime[1]=false;
	for(int i=2; i*i<=MAX; i++){
		if(!is_prime[i]) continue;
		for(int j=2*i; j<=MAX; j+=i){
			is_prime[j]=false;
		}
	}
}

int main(){
	get_prime();
	vector<int> v(MAX+1,0);
	for(int i=1; i<=MAX; i+=2){
		v[i]=v[i-2];
		if(is_prime[i] && is_prime[(i+1)/2]) v[i]++;
	}

	int q;
	cin >> q;
	for(int i=0; i<q; i++){
		int l, r;
		cin >> l >> r;
		if(l==1) cout << v[r] << endl;
		else cout << v[r]-v[l-2] << endl;
	}
	return 0;
}

Measured memory_bytes: 1024
n = gets.to_i
d, x = gets.chomp.split.map(&:to_i)
arr = []
n.times{arr << gets.to_i}
sum = 0
arr.each{|a|
    b = 0
    while a * b + 1 <= d
        sum += 1
        b += 1
    end
}
puts sum + x

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define PRINT(v) for (auto x : (V)) cout <<x <<" " <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> struct edge { int from, to; T cost;};
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;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }


int main() {
  ll a,b; cin >>a >>b;
  if (a*b <= 0){
    cout <<"Zero" <<endl; return 0;
  }
  if (a > 0){
    cout <<"Positive" <<endl; return 0;
  }
  if ((b - a) % 2 == 0){
    cout <<"Negative" <<endl;
  }else{
    cout <<"Positive" <<endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    char n;
    int64_t sum=0;
    while (cin >> n){
        //cin >> n;
        sum += n - '0';
        sum = sum % 9;
    }
    if (sum % 9 == 0)cout << "Yes" << '\n';
    else cout << "No" << '\n';

    return 0;
}

Measured memory_bytes: 3628
import kotlin.math.*

fun main() {
    val (a, b, h, m) = readLine()!!.split(" ").map(String::toDouble)
    val aK = 30.0 * h + 0.5 * m
    val bK = 6.0 * m

    val diff = Math.toRadians(abs(aK - bK))
    val result = sqrt((a * sin(diff)).pow(2.0) + (b - a * cos(diff)).pow(2.0))
    println(result)
}

Measured memory_bytes: 36612
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
const int INF = 1 << 29;
const double EPS = 1e-9;
 
typedef long long ll;
 
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
 
 
char A[105];
char B[105];
int main(int argc, char * argv[])
{
    ios::sync_with_stdio(false);
    cin >> A >> B;
    int flag = 0;
    if (strlen(A) > strlen(B)) {
        cout << "GREATER" << endl;
        return 0;
    }
    if (strlen(A) < strlen(B)) {
        cout << "LESS" << endl;
        return 0;
    }
    rep(i, 100) {
        if ((int)A[i] == 0) {
            break;
        }
        if (A[i] > B[i]) {
            cout << "GREATER" << endl;
            return 0;
        }
        if (A[i] < B[i]) {
            cout << "LESS" << endl;
            return 0;
        }
    }
    cout << "EQUAL" << endl;
 
    return 0;
}


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

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

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

	if(A[0] % 2 == 0 && A[0] == A[1] && A[0] == A[2]) {
		cout << -1 << endl;
		return 0;
	}

	int ans = 0;
	while(A[0] % 2 == 0 && A[1] % 2 == 0 && A[2] % 2 == 0) {
		int B[3] = { 0 };
		for(int i = 0; i < 3; i++) {
			for(int j = 0; j < 3; j++) {
				if(i == j) continue;
				B[j] += A[i] / 2;
			}
		}

		for(int i = 0; i < 3; i++) {
			A[i] = B[i];
		}
		ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scanner = new Scanner(System.in);
		String sample = scanner.nextLine();

		// A C G T
		int max = 0;
		int temp = 0;
		String[] s = sample.split("");

		for(String a : s){
			if(a.equals("A") || a.equals("G") || a.equals("C") || a.equals("T")){
				temp++;
				if(temp > max){
					max = temp;
				}
			}else{
				if(temp > max){
					max = temp;
				}
				temp = 0;
			}
		}
		System.out.println(max);
	}
}


Measured memory_bytes: 23124
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace AtCoder
{
    class Program
    {
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static int Solve(int N, string A, string B, string C)
        {
            int sum = 0;
            for (int i = 0; i < N; ++i)
            {
                var set = new HashSet<char> { A[i], B[i], C[i] };
                sum += set.Count - 1;
            }
            return sum;
        }

        static void Main(string[] args)
        {
            int N = ReadInt();
            var A = Read();
            var B = Read();
            var C = Read();
            Console.WriteLine(Solve(N, A, B, C));
        }
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
#define ft first
#define sc second
#define pt(sth) cout << sth << "\n"
#define moca(a, s, b) a=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
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;}
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;

//for(i=0; i<N; i++) cin >> a[i];

ll mem[3333][3333][5];
ll a[3333][3333];
ll R, C, K;

ll rec(ll x, ll y, ll k) {
  if(mem[x][y][k]!=-1) return mem[x][y][k];
  
  ll res=0;
  
  if(x+1<R) {
    if(a[x+1][y]>0) {
      chmax(res, rec(x+1, y, 1)+a[x+1][y]);
      chmax(res, rec(x+1, y, 0));
    }else {
      chmax(res, rec(x+1, y, 0));
    }
  }
  
  if(y+1<C) {
    if(a[x][y+1]>0) {
      if(k+1<=3)
        chmax(res, rec(x, y+1, k+1)+a[x][y+1]);
      
      chmax(res, rec(x, y+1, k));
    }else {
      chmax(res, rec(x, y+1, k));
    }
  }
  
  return mem[x][y][k]=res;
  
}

int main(void) {
  ll i, j, k;
  
  cin >> R >> C >> K;
  
  for(i=0; i<K; i++) {
    ll r, c, v;
    cin >> r >> c >> v;
    r--; c--;
    a[r][c]=v;
  }
  
  for(i=0; i<R; i++) for(j=0; j<C; j++) for(k=0; k<5; k++)
    mem[i][j][k]=-1;
  
  pt(max(rec(0, 0, 0), rec(0, 0, 1)+a[0][0]));
  
}
 
 




Measured memory_bytes: 445408
n = int(input())
d = []
for i in range(n):
    d.append(int(input()))
res = 0
for i in range(len(d)):
    a = 1
    some = d[i]
    if(i > 0):
        for j in range(i):
            if(some == d[j]):
                a = 0
                break
    res = res + a
print(res)


Measured memory_bytes: 3060
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int n = in.nextInt();
		int d = in.nextInt();
		int[][] x = new int[n][d];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < d; j++)
				x[i][j] = in.nextInt();
		System.out.println(solve(x));
		in.close();
	}

	private static int solve(int[][] x) {
		int r = 0;
		for (int i = 0; i < x.length; i++)
			for (int j = i + 1; j < x.length; j++)
				if (isOk(x[i], x[j]))
					r++;
		return r;
	}

	private static boolean isOk(int[] a, int[] b) {
		long r = 0;
		for (int i = 0; i < a.length; i++)
			r += Math.pow(a[i] - b[i], 2);
		long r2 = (long) Math.pow(r, 0.5);
		if (r2 * r2 == r)
			return true;
		else
			return false;
	}
}


Measured memory_bytes: 23124
fun main(arr: Array<String>) {
    val s = readLine()!!.toLong()
    val x1 = 0
    val y1 = 0
    val max = 1000000000L
    val y3 = if(s%max==0L) 0 else (max - (s%max))
    val x2 = 1L
    val y2 = max
    val x3 = s/max + Math.min(1, s%max)
    println("$x1 $y1 $x2 $y2 $x3 $y3")

//    println(s)
//    println(Math.abs(x3*y2-x2*y3))
}


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}


const ll MOD = 1e9 + 7;


struct UnionFind {
  vector<int> data; // 根の場合は集合の大きさ*-1、子の場合は親の番号が入る
  UnionFind(int size) : data(size, -1) { }
  bool link(int x, int y) { //新たな併合を行うとtrue
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  int root(int x) { // 代表元を返す
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) { // 要素xが含まれる集合の大きさ
    return -data[root(x)];
  }
  bool same(int x, int y) { // 同じ集合ならtrue
    return root(x) == root(y);
  }
};


ll mod_pow(ll a, ll b, ll p) {
  ll res = 1;
  while (b > 0) {
    if (b & 1) res = (res * a) % p;
    a = (a * a) % p;
    b >>= 1;
  }
  return res;
}

struct Edge {
  int a, b;
  ll w;
};

vector<vector<int>> g;
vector<Edge> es;
int N, M;

vector<ll> hist;
void dfs(int from, int to, int prev, const vector<int>& use) {
  if (from == to) {
    throw 42;
  }
  for (int i : g[from]) if (i != prev && use[i]) {
    int nxt = from ^ es[i].a ^ es[i].b;
    hist.push_back(es[i].w);
    dfs(nxt, to, i, use);
    hist.pop_back();
  }
}

// コストx以下の全域木はすべて単色であるような、辺の塗り方の場合の数
ll f(const ll x) {

  vector<int> use(M);
  UnionFind uf(N);

  ll mst_size = 0;
  for (int i = 0; i < (int)es.size(); i++) {
    const Edge& e = es[i];
    if (uf.link(e.a, e.b)) {
      mst_size += e.w;
      use[i] = 1;
    }
  }

  if (mst_size > x) return mod_pow(2, M, MOD);
  ll res = 2;

  for (int i = 0; i < (int)es.size(); i++) if (!use[i]) {
    const Edge& e = es[i];

    hist.clear();
    try {
      dfs(e.a, e.b, -1, use);
    } catch (int e) {
    }
    ll ma = *max_element(ALL(hist));
    ll diff = e.w - ma;

    if (mst_size + diff > x) res = (res * 2) % MOD;
  }
  return res;
}

int main2() {
  N = nextLong();
  M = nextLong();
  ll X = nextLong();

  es.clear();
  g = vector<vector<int>>(N);

  REP(i, M) {
    int a = nextLong() - 1;
    int b = nextLong() - 1;
    ll w = nextLong();
    es.push_back((Edge){a, b, w});
  }

  sort(ALL(es), [](const Edge&a, const Edge&b) {
    return a.w < b.w;
  });

  REP(i, M) {
    g[es[i].a].push_back(i);
    g[es[i].b].push_back(i);
  }

  ll ans = f(X-1) - f(X);
  ans = (ans % MOD + MOD) % MOD;
  cout << ans << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

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

int main() {
    std::string x;
    std::cin >> x;
    int ret = 0, counter = 0, s = 0, t = 0;
    for (auto c : x) {
        if (c == 'S') counter++, s++;
        else {
            if (counter > 0) counter--, t++;
            else ret++;
        }
    }

    std::cout << ret + s - t << std::endl;
    return 0;
}

Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC167B
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int A = int.Parse(input[0]);
            int B = int.Parse(input[1]);
            int C = int.Parse(input[2]);
            int K = int.Parse(input[3]);
            int count = 0;
            if (K <= A)
            {
                count = K;
            }
            else if (K <= A + B)
            {
                count = A;
            }
            else
            {
                count=2*A + B - K;
            }
            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 27544
#include <iostream>
#include <vector>

using namespace std;

int main(){
  int s, max, min, ans, k;
  vector<int> vec;
  for (int i=0; i < 6; i++) {
    cin >> s;
    vec.push_back(s);
  }

  k = vec[5];
  remove(vec.begin(), vec.end(), k);
  min = *min_element(vec.begin(), vec.end());
  max = *max_element(vec.begin(), vec.end());
  ans = max - min;

  if (k >= ans) {
    cout << "Yay!" << endl;
  } else {
    cout << ":(" << endl;
  }
}

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


int main(){
  int A,B,K;
  cin>>A>>B>>K;
  priority_queue<int> S;
  int C=1;
  while(C<=min(A,B)){
    if(A%C==0 && B%C==0){
      S.push(C);
    }
    ++C;
  }

  int count=1;
  while(count<K){
    S.pop();
    ++count;
  }

  cout<<S.top()<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
typedef double ll;
#define pb push_back
#define MP make_pair

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int a,b;
    string s,u,t;
    cin>>s>>t;
    cin>>a>>b;
    cin>>u;
    if(u==s)
    a--;
    else
    b--;
    cout<<a<<" "<<b;

    
     
    
     return 0;
}


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


void solve(std::string S){
    if (S == "Sunny") {
        cout << "Cloudy" << endl;
    } else if (S == "Cloudy") {
        cout << "Rainy" << endl;
    } else if (S == "Rainy") {
        cout << "Sunny" << endl;
    }
}

// Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


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

#define ll long long
#define pb push_back

const int maxn = 3e5 + 20;

int pos[maxn] , a[maxn];

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

	int n;
	cin >> n;

	for(int i = 0; i < n; i++)
		cin >> a[i] , a[i]-- , pos[a[i]] = i;

	set<int> st;
	st.insert(-1);
	st.insert(n);

	ll res = 0;
	for(int i = n - 1; i >= 0; i--)
	{
		int k = pos[i];

		auto R = st.lower_bound(k);
		auto L = R;
		L--;

		if(*R != n)
		{
			auto tmp = R;
			tmp++;
			res += 1LL * (i + 1) * (*tmp - *R) * (k - *L);
		}
		if(*L != -1)
		{
			auto tmp = L;
			tmp--;
			res += 1LL * (i + 1) * (*R - k) * (*L - *tmp);
		}

		st.insert(k);
	}

	cout << res << endl;
}










 


Measured memory_bytes: 5760
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (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; }
typedef long long ll;
typedef pair<int,int> P;

double dp[3005][3005];
double p[3005];

int main(){
    int n;
    cin >> n;
    rep(i,n)cin >> p[i+1];
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            if(j-1>=0)dp[i][j]+=dp[i-1][j-1]*p[i];
            dp[i][j]+=dp[i-1][j]*(1-p[i]);
        }
    }
    double ans = 0;
    for(int i=n/2+1;i<=n;i++)ans += dp[n][i];
    printf("%.10f\n",ans);
}

Measured memory_bytes: 68992
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

int main() {
    long long int n;
    cin >> n;
    n *= 2;
    long long int res = -1;
    for (long long int i = 1; i * i <= n; i++) {
    	if (n % i == 0) {
    		long long int p = i, q = n / p;
    		vector<long long int> v1{p, q}, v2{0, q - 1};
    		auto ret = crt(v2, v1);
    		if (ret.first != 0) {
    			if (res == -1 || res > ret.first) {
    				res = ret.first;
    			}
    			// cout << ret.first << " " << ret.second << " " << p << " " << q << endl;
    		}
    	

	    	swap(p, q);
	    	v1 = vector<long long int>{p, q};
	    	v2 = vector<long long int>{0, q - 1};
	    	ret = crt(v2, v1);
	    	if (ret.first != 0) {
				if (res == -1 || res > ret.first) {
					res = ret.first;
				}
				// cout << ret.first << " " << ret.second << " " << p << " " << q << endl;
			}
		}
    }
    cout << res << endl;
}






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

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> A(n);
    for(int& i: A) cin >> i;
    multiset<int> mn;
    mn.insert(A[0]);
    for(int i = 1; i < n; i++){
        auto it = mn.lower_bound(A[i]);
        if(it == mn.begin()) mn.insert(A[i]);
        else{
            mn.erase(--it);
            mn.insert(A[i]);
        }
    }
    cout << mn.size() << endl;
}

Measured memory_bytes: 5376
#include <stdio.h>
int main(){    
char number[1001];    
int i, sum;    
while(1){        
scanf("%s", number);        
if(number[0]=='0')break;        
sum=0;       
 for(i=0;number[i]!='\0';i++){            
sum+=number[i]-'0';        }        
printf("%d\n", sum);    }    
return 0;
}


Measured memory_bytes: 2052