akhauriyash/Code-Regression huggingface dataset:
/*
Hanit Banga
*/

#include <iostream>
#include <vector>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false)

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 1e5 + 5;

ll a[N];

int main()
{
	ll n;
	cin >> n;

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

	a[n] = a[0];
	ll x = n*(n + 1)/2 + 1, den = (x - 1) * n;

	// cout << x << ' ' << den << endl;

	for (int i = 0; i < n; ++i)
	{
		ll temp = sum - a[i] - a[i + 1] + x*a[i] - (x - 2)*a[i + 1];
		if (temp < 0 or temp % den)
		{
			cout << "NO";
			return 0;
		}
	}

	cout << "YES";
}

Measured memory_bytes: 1152
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;

int main() {
  int N;
  cin >> N;
  vector<double> t(N), v(N);
  for (int i = 0; i < N; i++) {
    cin >> t[i];
  }
  for (int i = 0; i < N; i++) {
    cin >> v[i];
  }
  vector<double> bounds(N + 1, 0);
  for (int i = N - 1; i >= 1; i--) {
    bounds[i] = min({bounds[i + 1] + t[i], v[i], v[i - 1]});
  }
  double res = 0, cur = 0;
  for (int i = 0; i < N; i++) {
    double nxt = min(cur + t[i], bounds[i + 1]);
    double x = (t[i] + nxt - cur) / 2.0;
    double a = min(v[i] - cur, x);
    double b = min(v[i] - nxt, t[i] - x);
    res += (cur + (cur + a)) * a / 2.0;
    res += (nxt + (nxt + b)) * b / 2.0;
    res += v[i] * (t[i] - a - b);
    cur = nxt;
  }
  printf("%.10f\n", res);
  return 0;
}


Measured memory_bytes: 256
import java.util.TreeMap;
import java.util.Map;
import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Map<String, Integer> map = new TreeMap<>();
		int max = 0;
		for(int i=0;i<n;i++){
			String s = sc.next();
			int c = 0;
			if(map.containsKey(s)){
				c = map.get(s);
			}
			map.put(s, ++c);
			if(max<c){
				max = c;
			}
		}
		sc.close();
		int com = max;
    	// 出現回数降順
		map.entrySet().stream()
			.filter(s -> s.getValue()==com)
        	.sorted(java.util.Collections.reverseOrder(java.util.Map.Entry.comparingByValue()))
        	.forEach(s -> System.out.println(s.getKey()));
	}
}

Measured memory_bytes: 87108
#include <iostream>
#include <array>

using namespace std;

static void inputArray(int A[], int num) {
  for (int i = 0; i < num; i++) {
    cin >> A[i]; 
  }
}

int main() {
  array<int, 10000> N;
  array<int, 500> Q;
  int s, t;

  cin >> s;
  inputArray(&N[0], s);

  cin >> t;
  inputArray(&Q[0], t);

  int found = 0;
  for (int i = 0; i < t; i++) {
    for (int j = 0; j < s; j++) {
      if (N[j] == Q[i]) {
        found++; 
        j = N.size();
      }
    } 
  }
  cout << found << endl;  

  return 0;
}



Measured memory_bytes: 3144
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

template <typename T> inline T read(){
    T sum = 0;
    int fl = 1,ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
    for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
    return sum * fl;
}

const double PI = 3.1415926535;

double a,b,x;

inline void Solve (){
	double tmp = x * 2.0 / (b * a);
	if(tmp <= a){
		printf("%.10lf",atan(b / tmp) / PI * 180);
	}else{
		double fix = (2 * x - a * a * b) / (a * a);
		b -= fix;
		double ntmp = x * 2.0 / (b * a);
		printf("%.10lf",atan(b / a) / PI * 180);
	}
}

inline void Input (){
	a = read<int>();
	b = read<int>();
	x = read<int>();
}

int main(){
	Input();
	Solve();
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
#include <cmath>
#include <utility>
#include <numeric>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i=0;(i)<(n);(i)++)
#define repi(i, n) for (int i=0;(i)<=(n);(i)++)
#define repr(i, n) for (int i=n;(i)>=0;(i)--)
#define print(x) (cout<<x<<endl)

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

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

int main() {
    int N; cin>>N;
    ll t=1LL;
    rep(i,N) {
        ll T; cin>>T;
        t = lcm(t, T);
    }
    print(t);
}

Measured memory_bytes: 256
alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k',
			'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
			'w','x', 'y', 'z']

dic = {}
for c in alphabet:
	dic[c] = 0

while True:
	try:
		string = list(input().rstrip().lower())
	except EOFError:
		break

	for c in string:
		if c in alphabet:
			dic[c] = dic[c] + 1

for key in dic:
	print('{} : {}'.format(key, dic[key]))


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

// definition {{{ 1

// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)

#define Scll(x) scanf("%llu", &x)
#define Scll2(x,y) scanf("%llu%llu", &x, &y)
#define Scll3(x,y,z) scanf("%llu%llu%llu", &x, &y, &z)

#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2

// constants {{{ 2
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
// }}} 2

// systems {{{ 2
#define Rep(x,y) for(int x = 0; x < y; x++)
#define Repe(x,y,z) for(int x = z; x < y; x++)
// }}} 2

// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n");
// }}} 2

// }}} 1

int main() {

    int N,T;
    Scd2(N,T);

    int t;
    int tmp = 0;
    Scd(t);
    ll ans = 0;
    Repe(i,N,1){
        tmp = t;
        Scd(t);
        ans += min(T,t-tmp);
    }
    ans += T;

    printf ("%llu\n", ans);

    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin >> N;

vector<int> A(N);
A.at(0)=0;

map <int ,int> ans ;
for (int i = 2; i <= N; i++)
{
    cin >> A.at(i-1);
}

ans[0]=0;

for (int i = 0; i < N; i++) ans[i];

for (int i = 1; i < N; i++)
{
    ans[A.at(i)-1] ++ ;
}


for (auto ai :ans){
cout << ai.second << endl;

}



}


Measured memory_bytes: 13556
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vii = vector<ii>;
const int oo = 1e8+7;
const int mod = 1e9+7;

int n;
vector<vi> edges;
vector<vector<ll>> dp;

#define b first
#define w second

ll mult(ll a, ll b) {    
    ll x = ll(a * b) % mod;
    return x;
}

ll add(ll a, ll b) { 
    ll x = a + b;
    if(x >= mod) {
        x -= mod;
    }
    return x;
}


// c = 0 -> white, c = 1 -> black
ll dfs(int a, int parent, int c) {
    
    if(dp[a][c] != -1) return dp[a][c];
    
    ll ans = 1;
    
    for(int& b : edges[a]) if(b != parent) {
        
        if(c == 0) {
            ans = mult(ans, add(dfs(b, a, 0),dfs(b, a, 1))); 
        } else if(c == 1) {
            ans = mult(ans, dfs(b, a, 0));
        }
    
    }

    dp[a][c] = ans;
    return ans;
}

int main() {
   
    scanf("%d",&n);
    edges.resize(n+1);
    dp.assign(n+1, vector<ll>(2, -1));
    
    for(int i = 0; i < n-1; ++i) {
        int a, b;
        scanf("%d%d",&a,&b);
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    
    ll ans1 = dfs(1, -1, 0);
    ll ans2 = dfs(1, -1, 1);
    
    cout << add(ans1, ans2) << endl;
    
    return 0;
}




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

#define ll long long 
#define endl "\n"
#define PI 3.141592653589793

const ll int MOD=1e9+7;

void solve()
{
	int a,b,h,m;
	double x1,x2,theta,x;
	cin >> a >> b >> h >> m;
	x1 = h*30 + m*(0.5);
	x2 = m*6;
	theta = min(abs(x1-x2),360-abs(x1-x2));
	x = sqrt(a*a + b*b - 2*a*b*cos((theta*PI)/180));
	cout << setprecision(15)<<x<< endl;
}

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

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

int main(){
  string S;
  cin >> S;
  if(S=="Sunny"){
    cout << "Cloudy" << endl;
    return 0;
  }else if(S=="Cloudy"){
    cout << "Rainy" << endl;
    return 0;
  }else{
    cout << "Sunny" << endl;
    return 0;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pb push_back
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f
#define endl '\n'
#define ll long long
#define f first
#define int long long
#define s second
#define FAST cin.tie(0), cout.tie(0), ios::sync_with_stdio(0)
#define debug(x) cout << "DEBUG " << x << endl
#define debug2(x, y) cout << "DEBUG " << x << " " << y << endl
#define debug3(x, y, z) cout << "DEBUG " << x << " " << y << " " << z<< endl
#define debug4(x, y, z, o) cout << "DEBUG " << x << " " << y << " " << z<< " " << o << endl
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pair<int, int>> ppi;
typedef vector<vector<int>> mat;
const ll mod = 1e9+7;
const int MAXN = 2*1e5+10;

vector<int> g[MAXN];
int sum[MAXN];

void dfs(int u, int p) {

	for(auto i : g[u]) {
		if(i == p) continue;
		sum[i] += sum[u];
		dfs(i, u);
	}
	
}

int32_t main() {
	int n, q;
	cin >> n >> q;
	for(int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	while(q--) {
		int u, x;
		cin >> u >> x;
		u--;
		sum[u] += x;
	}
	
	dfs(0, 0);

	for(int i = 0; i < n; i++) 
		cout << sum[i] << " ";
	
	cout << endl;
}


Measured memory_bytes: 24320
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define inf LLONG_MAX
#define pll pair <ll,ll>
#define min_pq priority_queue <pll> ,vector <pll>, greater <pll> > > 
#define f first
#define s second

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


	ll n;
	cin>>n;
	ll a[n],b[n],c[n];
	for(ll i=0;i<n;i++)
		cin>>a[i]>>b[i]>>c[i];
	ll dp1[n],dp2[n],dp3[n];
	memset(dp1,0,sizeof dp1);
	memset(dp2,0,sizeof dp2);
	memset(dp3,0,sizeof dp3);
	dp1[0]=a[0];
	dp2[0]=b[0];
	dp3[0]=c[0];

	for(ll i=1;i<n;i++)
	{
		dp1[i]=a[i]+max(dp2[i-1],dp3[i-1]);
		dp2[i]=b[i]+max(dp1[i-1],dp3[i-1]);
		dp3[i]=c[i]+max(dp1[i-1],dp2[i-1]);
	}
	cout<<max(max(dp1[n-1],dp2[n-1]),dp3[n-1])<<'\n';
}	


Measured memory_bytes: 4992
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include<map>
#include <iomanip>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
using namespace std;
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
#define LONGINF 1000000000000000000
int main() {
	string s;
	cin >> s;
	int cnt = 0;
	for (int i = 1;i < s.length();++i) {
		if (s[i] != s[i - 1])cnt++;
	}
	cout << cnt << endl;
	return 0;
}

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

int main() {
  int k;
  cin >> k;
  
  vector<int> vec = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  cout << vec.at(k - 1);
  
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
long long mod=1000000007;
int c[5100];
int d[5100];
int dp[5100][5100];
int sum[5100][5100];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%d",c+i);
	for(int i=0;i<a;i++)scanf("%d",d+i);
	for(int i=c[0];i<b;i+=d[0]){
		dp[1][i]=1;
		if(d[0]==0)break;
	}
	sum[1][0]=dp[1][0];
	for(int i=1;i<b;i++){
		sum[1][i]=(dp[1][i]+sum[1][i-1])%mod;
	}
	for(int i=1;i<a;i++){
		for(int j=c[i];j<b;j+=d[i]){
			if(j)dp[i+1][j]=sum[i][j-1];
			if(d[i]==0)break;
		}
		for(int j=1;j<b;j++)sum[i+1][j]=(dp[i+1][j]+sum[i+1][j-1])%mod;
	}
	printf("%lld\n",sum[a][b-1]);
}

Measured memory_bytes: 203800
import java.util.*;

public class Main {
	static boolean check(String s) {
		if(s.charAt(0) != 'A')return false;
		boolean flag = false;
		for(int i = 1;i < s.length();i ++) {
			if(s.charAt(i) != 'C') {
				if(s.charAt(i) >= 'A' && s.charAt(i) <= 'Z')return false;
			}
			else if(flag || i < 2 || s.length() - i < 2)return false;
			else flag = true;
		}
		return flag;
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String s = in.nextLine();
		if(check(s)) {
			System.out.println("AC");
		}
		else {
			System.out.println("WA");
		}
	}
}


Measured memory_bytes: 21844
#include<stdio.h>

int main(void)
{
	int i;
	int no;
	int v[100];
	
	scanf("%d",&no);
	for(i=0;i<no;i++){
		scanf("%d",&v[i]);
	}
	for(i=no;i>0;i--){
		printf("%d",v[i-1]);
		if(i == 1){
			break;
		}
		printf(" ");
	}
	printf("\n");
	return 0;
}

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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0;i < n;i++){
        cin >> a.at(i);
    }
    sort(a.begin(),a.end(),greater<int>());
    int ans = 0;
    for (int i = 0;i < n - 1;i++){
        if (a.at(i) == a.at(i+1)){
            continue;
        }
        else{
            ans += a.at(i) - a.at(i+1);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
  int top,stack[101];
  char input[8];

  top = 0;
  while( scanf("%s",input) != EOF ){
    if( '+' == input[0] ){
      top--;
      stack[top] += stack[top+1];
    }
    else if( '-' == input[0] ){
      top--;
      stack[top] -= stack[top+1];
    }
    else if( '*' == input[0] ){
      top--;
      stack[top] *= stack[top+1];
    }
    else{
      top++;
      stack[top] = atoi(input);
    }
  }
  printf("%d\n",stack[top]);
  return 0;
}

Measured memory_bytes: 548
#include <bits/stdc++.h>
#include <fstream>
#include <cstdio>
using namespace std;
// vector<pair<int,int> > v;
// cin.ignore();//twice getline(cin,s);
// g++ iterator.cpp -std=c++17
// cout<<(A + B == C ? "YES" : "NO")<<endl;
// __gcd(a,b)
// string s=to_string(n);
// string p=s.substr(0,len);
// string q=s.insert(0,str);
// sort(arr, arr+n, greater<int>());
// cout<<fixed<<setprecision(9)<<pi<<endl
// const  double pi = acos(-1.0);
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define vll vector<ll>
#define mll map<ll,ll >
#define mlli map<ll,ll>::iterator
#define size size()
#define endl "\n"
#define ll long long int
#define ld long double
void fast(){ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);}


int main(void)
{
	fast();
	ll n,d;
	cin>>n>>d;
	ll cnt=0;
	for(int i=0;i<n;i++)
	{
		ll x,y;
		cin>>x>>y;
		ll pans = (x*x)+(y*y);
		double ans = sqrt(pans);
		if(ans<=double(d))
		{
			cnt++;
		}
	}	
	cout<<cnt<<endl;
}

Measured memory_bytes: 3664
#include<bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
using namespace std;

//ループマクロ
#define FOR(i , a , b)  for(int i = (a) ; i < (b) ; i++)
#define REP(i , n)      for(int i = 0 ; i < n ; i++)
#define REPR(i , n)     for(int i = n ; 0 <= i ; i--)
#define ROP(i, n)       for(int i = 1 ; i <= n ; i++)

//入出力
#define SCOUT(x) cout << (x) << " "
#define VECCIN(x) for(auto& ele : (x) ) cin >> ele
#define VECOUT(x) for(auto& ele : (x) ) cout << ele << " "; cout << endl;

//その他
#define ALL(obj) (obj).begin() , (obj).end() 
#define SORT(obj) sort(ALL(obj))
#define GSORT(obj) sort(ALL(obj) , greater<int>())
#define P pair<int , int>
#define V vector<int>
#define VLL vector<long long>
#define M map<int, int>
#define S set<int>
#define PQ priority_queue<int>
#define PQG priority_queue<int , V , greater<int>>

int main(void) {

	ios::sync_with_stdio(false);	cin.tie(0);
    int n, m, x;  cin >> n >> m >> x;
    vector<vector<int>> book(n, vector<int>(m+1));
    REP(i, n){
      cin >> book[i][0];
      ROP(j, m)  cin >> book[i][j];
    }

    int min_money = INF;
    for(int bit = 0 ; bit < (1<<n) ; bit++){
      
      V und(m, 0);  //各アルゴリズムに対する理解度
      int kp_money = 0;
      for(int i = 0 ; i < n ; i++){
        
        if(bit & (1<<i)){
          for(int j = 0 ; j < m ; j++)  und[j] += book[i][j+1];
          kp_money += book[i][0];
        }
      }

      bool is_all_clear = true;
      REP(i, m)
        if(und[i] < x)  is_all_clear = false;
      min_money = ((is_all_clear)? min(min_money, kp_money) : min_money);
    }

    cout << ((min_money != INF) ? min_money : -1) << endl;
	return 0;
}


Measured memory_bytes: 3668
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <cctype>
#define ll long long
#define PI 3.14159265358979323846
using namespace std;
const int maxn = 1e6+7;

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


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

using namespace std;

int main(){
    string s,S="";
    long long int A=0,ans=0;
    cin >> s;
    for(int i=0;i<s.size();i++){
        if(i!=s.size()-1 && s[i]=='B' && s[i+1]=='C'){
            S += 'D';
            ++i;
        }else{
            S += s[i];
        }
    }

    for(int i=0;i<S.size();i++){
        if(S[i]=='A'){
            A++;
        }else if(S[i]=='D'){
            ans += A;
        }else{
            A = 0;
        }
    }

    cout << ans << endl;
}

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

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define X first
#define Y second

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cout << #a << " = " << a << endl;

const double PI = acos(-1.0);
const LL INF = 1e9 + 7;
const LL LINF = INF * INF;

int n;
const int MAX = 3007;
double dp[MAX][MAX];
double p[MAX];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("In.txt", "r", stdin);
	//freopen("In.txt", "w", stdout);

	cin >> n;
	FOR(i, 1, n + 1)
		cin >> p[i];
	
	dp[0][0] = 1;
	FOR(i, 1, n + 1)
	{
		dp[i][0] = dp[i - 1][0] * (1.0 - p[i]);
		FOR(j, 1, i + 1)
			dp[i][j] = dp[i - 1][j] * (1.0 - p[i]) + dp[i - 1][j - 1] * p[i];
	}
	
	double ans = 0;
	FOR(i, n / 2 + 1, n + 1)
		ans += dp[n][i];
	
	cout << fixed << setprecision(10) << ans << endl;
	cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
	return 0;
}



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

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

int main() {
  int N;
  string S, T;
  cin >> N >> S >> T;
  vector< pair< int, int > > out[26];
  for(int i = 0; i < N; i++) {
    out[T[i] - 'a'].emplace_back(i, 0);
  }
  for(int i = 0; i < N; i++) {
    int buf;
    {
      auto &it = out[T[i] - 'a'];
      auto v = lower_bound(begin(it), end(it), make_pair(i, -1)) - begin(it);
      buf = it[v].second;
      if(i + 1 == N) cout << buf << endl;
      if(v + 1 < it.size()) (it[v + 1].second += buf) %= mod;
    }
    {
      auto &it = out[S[i] - 'a'];
      auto v = lower_bound(begin(it), end(it), make_pair(i, mod)) - begin(it);
      if(v < it.size()) (it[v].second += buf + (i == 0)) %= mod;
    }
  }
}



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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	vector<int> arr(n);
	for(int& x : arr) cin >> x;
	int br = 0, now = 1;
	
	for(int i = 0; i < n; i++) {
		if(arr[i] == now) {
			now++;
		} else {
			br++;
		}
	}
	
	if(br < n) {
		cout << br << endl;
	} else {
		cout << -1 << endl;
	}
}


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

namespace ABC115
{
    class Program
    {
        static void Main(string[] args)
        {
            string s;
            s = "Christmas";
            int a = int.Parse(Console.ReadLine());
           
            if (a <= 24)
            {
                s += " Eve";
                
            }
            if (a <= 23)
            {
                s += " Eve";
                
            }
             if (a <= 22)
            {
                s += " Eve";
               
            } Console.WriteLine(s);
            Console.ReadKey();
             }
    }
}

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

using namespace std;

vector<int> v[100010];
int dp[100010];

int len(int i)
{
    if(v[i].size()==0) return 0;
    if(dp[i]!=-1) return dp[i];
    else
    {
        int ans=0;
        for(int j=0;j<v[i].size();j++)
        {
            dp[i]=max(dp[i],1+len(v[i][j]));
        }
        return dp[i];
    }
}

int main()
{
    memset(dp,-1,sizeof dp);
    int n,m,x,y,lp=0;;
    cin>>n>>m;
    for(int i=0; i<m; i++)
    {
        cin>>x>>y;
        v[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        lp=max(lp,len(i));
    }
    cout<<lp;

}


Measured memory_bytes: 10624
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    int n,z,i;
    char s[1000];
    while(~scanf("%s",s))
    {
        n=0;
        for(i=0; i<4; i++)
        {
            if(s[i]=='+')
                n=n+1;
            else if(s[i]=='-')
                n=n-1;
        }
        printf("%d\n",n);
    }
    return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  sort(a.begin(), a.end() );
  int m, k;
  double l;
  m = a.back();
  k = m / 2;
  l = m / 2.0;
  int id = distance(a.begin(), lower_bound(a.begin(), a.end(), k) );
  k = (a[id]-l < l-a[id-1]) ? a[id] : a[id-1];
  cout << m << " " << k << endl;
  return 0;
}

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

using namespace std;

typedef long long ll;

const ll MOD = 998244353;

int n;
int arr[100002];
int cnt[100002];
ll ans=1;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
        cnt[arr[i]]++;
    }
    if(arr[1] || cnt[0] > 1){
        printf("0");
        return 0;
    }

    for(int i=1; i<n; i++){
        if(cnt[i]){
            for(int j=1; j<=cnt[i]; j++){
                ans *= cnt[i-1];
                ans %= MOD;
            }
        }
    }
    printf("%lld", ans);
}


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

#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()
#define CERR if(false) cerr
#define INT_MAX_HALF (INT_MAX / 2)
#define EPS (1e-10)

using namespace std;

typedef long long ll;



int main(){

    string s;
    cin >> s;

    if(s.size() % 2 == 0){
        bool b = true;

        rep(i, s.size() / 2){
            if(s[i * 2] == 'h' && s[i * 2 + 1] == 'i'){

            }else{
                b = false;
                break;
            }
        }

        if(b){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }else{
        cout << "No" << endl;
    }


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() 
{
    int n,m;
    cin>>n>>m;
    int a;
    for(int i=0; i<m; i++){
        cin>>a;
        n -= a;
    }
    if(n < 0){
        cout<<"-1"<<endl;
    }else{
        cout<<n<<endl;
    }
}


Measured memory_bytes: 3644
#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <float.h>
#include <stdlib.h>
#include <functional>
#include <limits>
#include <numeric>
#include <type_traits>
#include <queue>
#include <fstream>
#include <bitset>
#include <cmath>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i <= (int)(n); i++)
#define sort1(v) sort(v.begin(),v.end())
#define reverse(v) reverse(v.begin(),v.end())
#define all(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int,int> p;
bool paircom (pair<int,int> p,pair<int,int> q){
return p.second<q.second;
}

int main() {
       ll n,d;
    cin >>n>>d;
    ll a,b,ans;
    a=0;b=0;ans=0;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        ll dis=a*a+b*b;
        ll ku =d*d;
        if(dis<=ku)ans++;
    }
    
    cout <<ans;

}

    

Measured memory_bytes: 3584
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val (T, A) = readLine()!!.split(" ").map { it.toInt() }
    val xs = readLine()!!.split(" ").map { it.toInt() }

    var ans = 0
    var diff = Double.MAX_VALUE
    for ((index, p) in xs.withIndex()) {
        var t = T - p * 0.006
        if (Math.abs(A - t) < diff) {
            diff = Math.abs(A - t)
            ans = index + 1
        }
    }
    println(ans)
}

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

int main() {
    string s;
    cin >> s;
    for(int i = 0; i < s.length(); i++) {
        cout << 'x';
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>
#include <cmath>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

signed main() {
	int n,k;
	std::cin >> n >> k;
	std::map<int,std::vector<int> > map;
	rep(i,n) {
		int t,d;
		std::cin >> t >> d;
		map[t].emplace_back(d);
	}
	for(auto&&x:map) std::sort(all(x.second),std::greater<int>());
	// get the best of all varieties
	std::vector<int> best;
	for(auto x:map) best.emplace_back(x.second[0]);
	std::vector<int> rest;
	for(auto x:map) for(int i=1;i<x.second.size();i++) rest.emplace_back(x.second[i]);
	std::sort(all(best),std::greater<int>());
	std::sort(all(rest),std::greater<int>());
	std::vector<int> bac(best.size()+1,0);
	std::vector<int> rac(rest.size()+1,0);
	rep(i,best.size()) bac[i+1] = bac[i]+best[i];
	rep(i,rest.size()) rac[i+1] = rac[i]+rest[i];
	int max = 0;
	for(int t=1;t<=std::min(k,(int)best.size());t++) {
		if(t>best.size() || k-t>rest.size()) continue;
		int sum = t*t;
		sum+=bac[t];
		sum+=rac[k-t];
		max = std::max(max,sum);
	}
	print(max);

	return 0;
}


Measured memory_bytes: 12916
#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int main(){
    ll D, G;
    cin >> D >> G;
    vl p(D), c(D);
    rep(i, D) cin >> p[i] >> c[i];
    ll ans = INF;
    rep(mask, 1<<D) {
        ll cnt = 0LL, sum = 0LL;
        rep(i, D) {
            if(mask&(1<<i)) {
                cnt += p[i];
                sum += (i+1) * 100LL * p[i] + c[i];
            }
        }
        ll dif = G - sum;
        for(int i = D-1; i >= 0; --i) if((mask&(1<<i)) == 0) {
            if(dif < 0) break;
            ll tmp = dif / ((i+1) * 100LL);
            ll k = min(tmp, p[i]);
            dif -= (i+1)*100 * k;
            cnt += k;
        }
        if(dif > 0) continue;
        ans = min(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
	int h,m,s;
	int t;

	cin >> t;

	h = t / 3600;
	t = t - h * 3600;
	m = t / 60;
	s = t - m * 60;

	cout << h << ":" << m << ":" << s << endl;

	return 0;
}

Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
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;
}
typedef long long int ll;

#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define endl "\n"
const double EPS = 1e-7;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
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};

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

int n, x, y;
vector<vector<int>> g;
vector<int> ans(3000, 0);

void bfs(int s) {
    vector<int> d(n, INF);
    queue<int> que;
    d[s] = 0;
    que.push(s);
    while(que.size()) {
        int now = que.front();
        que.pop();
        if(d[now] == INF) {
            continue;
        }
        for(auto next : g[now]) {
            if(d[next] == INF) {
                d[next] = d[now] + 1;
                que.push(next);
            }
        }
    }
    for(int i = s; i < n; i++) {
        ans[d[i]]++;
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> x >> y;
    x--;
    y--;
    g.resize(n);
    for(int i = 0; i < n - 1; i++) {
        g[i].emplace_back(i + 1);
        g[i + 1].emplace_back(i);
    }
    g[x].emplace_back(y);
    g[y].emplace_back(x);
    for(int i = 0; i < n; i++) {
        bfs(i);
    }
    for(int i = 1; i < n; i++) {
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 384
def main():
    S = input()
    K = int(input())
    N = len(S)
    ans = 0
    from collections import Counter
    if N == 1:
        return print(K//2)
    tmp = 1
    for i in range(1,N):
        if S[i-1] == S[i]:
            tmp += 1
        else:
            ans += tmp // 2
            tmp = 1
    else:
        if tmp == N:
            ans = N*K//2
        else:
            ans += (tmp // 2)
            ans *= K
            if S[0] == S[-1]:
                first = 1
                for i in range(1,N):
                    if S[i-1] != S[i]:
                        break
                    first += 1
                last = 1
                for i in range(N-1,0,-1):
                    if S[i-1] != S[i]:
                        break
                    last += 1
                revise = first//2 + last//2 - (first+last)//2
                revise *= (K-1)
                ans -= revise
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 38384
import numpy as np
def cumsum(x):
    return list(np.cumsum(x))

def cumsum_number(N,K,x):
    ans=[0]*(N-K+1)
    number_cumsum = cumsum(x)
    number_cumsum.insert(0,0)
    for i in range(N-K+1):
        ans[i]=number_cumsum[i+K]-number_cumsum[i]
    return ans
"""
int #整数
float #小数

#for
for name in fruits: #fruitの頭から操作
    print(name)

#リスト
list0 = [] #リスト生成
list0 = [1,2,3,4] #初期化
list0 = [0]*10 #[0,0,0,0,0,0,0,0,0,0]
list1= [i for i in range(10)] #>>> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
list1 = list(map(int, input().split()))　# 複数の入力をリストに入れる
number=[int(input()) for i in range(int(input()))] #複数行の入力をリストに
list1 = list1 + [6, 7, 8] #リストの追加
list2.append(34) #リストの追加　最後に（）内が足される
list.insert(3,10) #リストの追加　任意の位置（追加したい位置,追加したい値）
len(list4) #リストの要素数
max(sa) #list saの最小値
list5.count(2) #リスト(文字列も可）内の2の数
list1.sort() #並び替え小さい順
list1.sort(reverse=True)  #並び替え大きい順
set(list1) #list1内の重複している要素を削除し、小さい順に並べる
sum([2,3,   ,3]) #リストの合計

abs(a) #aの絶対値
max(a,b) min(a,b) #最大値　最小値
text1 = text1.replace("34","test") #text1内の"34"を"test"に書き換える(文字列内の文字を入れ替える)

exit(0) #強制終了

cumsum(リスト) #累積和をリストで返す
cumsum_number(N,K,x) #N個の数が含まれるリストx内のK個からなる部分和をリストで返す
"""
N,A,B=map(int,input().split())
S=N//(A+B) #SはA+Bのセット数
M=N-S*(A+B) #Mは残り
if A<=M:
    print(A+S*A)
else:
    print(M+S*A)

Measured memory_bytes: 26932
N, K = map(int, input().split(' '))
w = [int(input()) for _ in range(N)]

def ok(p, k, w):
	sum = 0
	i = 0
	while i < len(w):
		if k == 0:
			return False
		sum += w[i]
		if sum > p:
			k -= 1
			sum = 0
		else:
			i += 1
	return True

l = 0
r = sum(w)
while l+1 < r:
	m = (l+r)//2
	if ok(m, K, w):
		r = m
	else:
		l = m

print(r)




Measured memory_bytes: 9564
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

#define rep(i, n) for (int i = 0; i < n; i++)
#define REP(i, a, n) for (int i = a; i < n; i++)
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eps 1e-15

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef tuple<int, int, int> ti3;

int main()
{
    int n, T;
    scanf("%d %d", &n, &T);

    int cost_min = numeric_limits<int>::max();

    rep(i, n)
    {
        int c, t;
        scanf("%d %d", &c, &t);
        if (t <= T && c < cost_min) {
            cost_min = c;
        }
    }
    if (cost_min == numeric_limits<int>::max()) {
        printf("TLE\n");
    } else {
        printf("%d\n", cost_min);
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int 
#define mod 1000000007
#define se second
#define fi first
#define endl "\n"
#define pi 3.1415926535897932384626433832795028841971
#define MAX 9223372036854775807
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
//	cout<<fixed<<setprecision(15);
	ll x,n;
	cin>>x>>n;
	set<ll> s;
	ll y,z;
	for(int a=0;a<n;a++)
	{
		cin>>y;
		s.insert(y);
	}
	if(s.find(x)==s.end())
	{
		cout<<x;
		return 0;
	}
	y=x+1;z=x-1;
	while(1)
	{
		if(s.find(z)==s.end())
		{
			cout<<z;
			return 0;
		}
		if(s.find(y)==s.end())
		{
			cout<<y;
			return 0;
		}
		z--;y++;
	}
	return 0;
}

Measured memory_bytes: 3664
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1167
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>
using ll = long long;
using namespace std;

#define MAX 1000000
int const MOD = 1e9 + 7;
vector<ll> full_set, odd_set;
int dp1[MAX], dp2[MAX]; //最小数, 最小数(奇数のみ)
int main(void)
{
    for (ll i = 1; i * (i + 1) * (i + 2) / 6 < MAX; ++i)
    {
        ll t = i * (i + 1) * (i + 2) / 6;
        if (t % 2 == 1)
        {
            odd_set.push_back(t);
        }
        full_set.push_back(t);
    }

    for (int i = 0; i < MAX; ++i)
    {
        dp1[i] = 1e9;
        dp2[i] = 1e9;
    }
    dp1[0] = 0;
    dp2[0] = 0;
    for (int i = 0; i < full_set.size(); ++i)
    {
        for (int j = 0; j < MAX; ++j)
        {
            if (j - full_set[i] >= 0)
                dp1[j] = min(dp1[j], dp1[j - full_set[i]] + 1);
        }
    }

    for (int i = 0; i < odd_set.size(); ++i)
    {
        for (int j = 0; j < MAX; ++j)
        {
            if (j - odd_set[i] >= 0)
            {
                dp2[j] = min(dp2[j], dp2[j - odd_set[i]] + 1);
            }
        }
    }
    ll n;
    while (cin >> n, n)
    {
        cout << dp1[n] << " " << dp2[n] << endl;
    }
    return 0;
}


Measured memory_bytes: 10988
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#define ll long long
#define PI 3.141592653589
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define EPS 1e-7
#define PII pair<int,int>
#define s second
#define f first
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
ll MOD = 1e9+7;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int random_int(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
ll fast_power(ll x, ll p){
    ll res = 1;
    while(p > 0){
        if(p & 1){
            res = (res * x)%MOD;
        }
        p = p >> 1;
        x = (x*x)%MOD;
    }
    return res;
}

int main() {
    IO;
    int n;
    cin >> n;
    double arr[n];
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    double dp[n+1][n+1]; // index heads
    for(int i = 0; i <= n; i++){
        dp[0][i] =  0;
    }
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= n; j++){
            dp[i][j] = 0;
            if(j > i){
                continue;
            }
            if(j != 0){
                dp[i][j] += dp[i-1][j-1] * arr[i-1];
            }
            dp[i][j] += dp[i-1][j] * (1-arr[i-1]);
        }

    }
    double ans = 0;
    for(int i = 0; i <= n; i++){
        if(n-i < i){
           ans += dp[n][i];
        }
    }
    cout << setprecision(10) << fixed << ans;

    return 0;
}


Measured memory_bytes: 70656
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const ll nmax = 8;
const ll INF = 1e9;
bool graph[nmax][nmax];
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}

class UnionFind
{
public:
    vector<ll> Parent;

    UnionFind(ll N)
    {
        Parent = vector<ll>(N, -1);
    }
    ll find(ll A)
    {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = find(Parent[A]);
    }

    ll size(ll A)
    {
        return -Parent[find(A)];
    }

    bool Union(ll A, ll B)
    {
        A = find(A);
        B = find(B);
        if (A == B)
        {
            return false;
        }
        if (size(A) < size(B))
            swap(A, B);

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }
};

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

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

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

ll ceil(ll a, ll b)
{
    return (a + b - 1) / b;
}

void solve(long long N, std::vector<long long> A)
{
    map<ll, ll> cnt;
    for (int i = 0; i < N; i++)
    {
        cnt[A[i]]++;
    }

    ll eat = 0;
    bool flag = false;
    for (auto &&i : cnt)
    {
        eat++;
    }

    if (eat % 2 == 0)
    {
        cout << eat - 1 << endl;
    }
    else
    {
        cout << eat << endl;
    }
}

int main()
{
    long long N;
    scanf("%lld", &N);
    std::vector<long long> A(N);
    for (int i = 0; i < N; i++)
    {
        scanf("%lld", &A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


Measured memory_bytes: 7296
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<math.h>
#include<queue>
#include<complex>
#include<random>
#include<ctime>
#include<set>
using namespace std;


const long long int mod=1000000007;
const long long int INF=99999999999999999;

long long int N,M,K,x[200000]={},res=0;

//階乗先に計算
class Kaizyou{
    public:
    long long int *kaizyou;
    Kaizyou(){};
    Kaizyou(long long int n,long long int mod){
        kaizyou=new long long int[n+1];
        kai(1,n,mod);
        return;
    }

    long long int kai(long long int a, long long int b, long long int mod) {
        long long int tmp = 1;
        for (long long int i = a; i <= b; i++) {
            tmp *= i;
            tmp %= mod;

            kaizyou[i] = tmp;
        }
        return tmp;
    }
};

//累乗(繰り返し2乗法)　aのb乗(mod)を求める。
class Ruizyou{
    public:
    long long int rui(long long int a, long long int b, long long mod) {
        int memo[65] = {};
        long long int A[65] = {};
        long long int tmp = 1;
        for (int i = 0; i < 65; i++) {
            memo[i] = b % 2;
            b /= 2;
        }

        A[0] = a;
        A[0] %= mod;

        for (int i = 1; i < 65; i++) {
            A[i] = A[i - 1] * A[i - 1];
            A[i] %= mod;
        }
        for (int i = 0; i < 65; i++) {
            if (memo[i] == 1) {
                tmp *= A[i];
                tmp %= mod;
            }
        }
        tmp %= mod;
        return tmp;
    }
};
string s[100],X;

int main() {
	cout<<setprecision(10);
	cin>>N;
	for(int i=1;i<=N;i++){
		cin>>x[i];
	}
	Kaizyou kai(200000,mod);
	Ruizyou ruirui;
	long long int tmp=kai.kaizyou[N-1];
	for(int i=2;i<=N;i++){
		res+=(x[i]-x[i-1])*tmp;
		tmp+=((kai.kaizyou[N-1]*ruirui.rui(i,mod-2,mod))%mod);
		tmp%=mod;
		res%=mod;
	}
	cout<<res<<endl;
} 


Measured memory_bytes: 2560
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
int main() {
    ll n;
    cin>>n;
    if(n>=400 && n<=599) cout<<"8";
    else if(n>=600 && n<=799) cout<<"7";
    else if(n>=800 && n<=999) cout<<"6";
    else if(n>=1000 && n<=1199) cout<<"5";
    else if(n>=1200 && n<=1399) cout<<"4";
    else if(n>=1400 && n<=1599) cout<<"3";
    else if(n>=1600 && n<=1799) cout<<"2";
    else if(n>=1800 && n<=1999) cout<<"1";
    else ;
        
}

Measured memory_bytes: 3632
#include <iostream>
using namespace std;
int main(void){
    int N,K;
    int a=1;
    cin >> N >> K;
    for (int i=1; i<=N ;i++){
        if (a*2<a+K){
            a=a*2;
        }
        else if (a*2>=a+K){
            a=a+K;
        }
        }
cout << a << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int a,b=0,c=100000;
  scanf("%d",&a);
  int d[a];
  for(int i=0; i<a; i++){
    scanf("%d",&d[i]);
    b+=d[i];
    if(d[i]%10!=0&&d[i]<c){
      c=d[i];
    }
  }
  if(b%10!=0){
    printf("%d",b);
  }else{
    b-=c;
    if(b<0){b=0;}
    printf("%d",b);
  }
  return 0;}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std; typedef long long ll; typedef unsigned long long ull; const int mod = 1e9 + 7;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define int ll

int N, W, w[101], v[101], dp[101][100001];

signed main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> W;
	memset(dp, 0, sizeof dp);
	for (int i = 1; i <= N; i++)
	{
		cin >> w[i] >> v[i];
	}
	for (int i = 0; i <= N; i++)
	{
		for (int j = 0; j <= W; j++)
		{
			if (i == 0 || j == 0)
			{
				dp[i][j] = 0;
			}
			else if (j >= w[i])
			{
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
			}
			else
			{
				dp[i][j] = dp[i - 1][j];
			}
		}
	}
	cout << dp[N][W];
}

Measured memory_bytes: 79232
#include "bits/stdc++.h"
using namespace std;
     
#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl
     
typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll, ll>
const int inf = 1000000001;
const ll INF = 1e16;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

int main() {
  int n;
  cin >> n;
  int sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += i;
    if (sum >= n) {
      break;
    }
  }
  int j = sum - n;
  for (int i = 1; i <= n; i++) {
    if (i == j) {
      continue;
    }
    cout << i << endl;
    n -= i;
    if (n == 0) {
      return 0;
    }
  }
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void)
{
    int n,i,j,k,ii,cnt,len,flg,f2,lenn;
    char nama[26];
    char ban[101];
     
    cnt=0;
    scanf("%d",&n);
    scanf("%s",nama);
    lenn=strlen(nama);
    for(i=0;i<n;i++) {
        scanf("%s",ban);
        len=strlen(ban);
        flg=0;
        for(j=0;j<len;j++)   {
			for(k=1;k+j<len;k++) {
				f2=1;
				for(ii=0;ii<lenn;ii++)   {
					if(j+k*ii>=len)    {
						f2=0;
						break;
					}
					if(nama[ii]!=ban[j+k*ii]) {
						f2=0;
						break;
					}
				}
				if(f2==1)   {
					flg=1;
					k=len; j=len;
				}
			}
        }
        if(flg==1)  {
            cnt++;
        }
    }
    printf("%d\n",cnt);
    return 0;
}


Measured memory_bytes: 600
s = input()
if "N" in s and "S" in s and "W" in s and "E" in s:
  print("Yes")
elif not "N" in s and not "S" in s and "W" in s and "E" in s:
  print("Yes")
elif "N" in s and "S" in s and not "W" in s and not "E" in s:
  print("Yes")
else:
  print("No")

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

int n;
int a[111];

int main(){
	cin>>n;
  rep(i,n)cin>>a[i];
  cout<<a[0];
  repl(i,1,n){
    cout<<" "<<a[i];
  }
  cout<<endl;
  repl(i,1,n){
    int v=a[i];
    int j=i-1;
    while(j>=0&&a[j]>v){
      a[j+1]=a[j];
      j--;
    }
    a[j+1]=v;
    cout<<a[0];
    repl(i,1,n){
      cout<<" "<<a[i];
    }
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 3072