akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

using namespace std;
using i64 = long long;

int main(){
    string s;
    cin>>s;
    i64 ans{};
    for(i64 i=0;i<s.size();i++) ans+=s[i]-'0';

    cout<<(ans%9==0?"Yes":"No")<<endl;

    return 0;
}

Measured memory_bytes: 3756
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
#include <deque>
#include <iomanip>
#include <limits>
#include <fstream>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;

struct BIT{
  int n;
  vector<ll> data;
  BIT(int n) : data(n + 1, 0), n(n){}
  ll sum(int i){
    ll s = 0;
    while(i > 0){
      s += data[i];
      i -= i & -i;
    }
    return s;
  }
  void add(int i, ll x){
    while(i <= n){
      data[i] += x;
      i += i & -i;
    }
  }
};

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  BIT B(n);
  FOR(i,0,q) {
    int com; cin >> com;
    int x, y;
    cin >> x >> y;
    if(com == 0) {
      B.add(x, y);
    } else {
      cout << B.sum(y) - B.sum(x-1) << endl;
    }
  }
  return 0;
}


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

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define REP2(i,n) for(int i=0;i<(int)(n);i++)
#define REP3(i,m,n) for(int i=m;i<(int)(n);i++)
#define REP4(i,m,n,s) for(int i=m;(s>0 and i<(int)(n)) or (s<0 and i>(int)(n));i+=s)
#define REP(...) GET_MACRO(__VA_ARGS__, REP4, REP3, REP2)(__VA_ARGS__)
#define REPIT(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define PIS(x) printf("%d ",x)
#define PN() putchar('\n')
#define MP make_pair
#define PB push_back
#define EB emplace_back

typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ULL;

void RI() {}
template<typename... T>
void RI( int& head, T&... tail ) {
    scanf("%d",&head);
    RI(tail...);
}
void print() {putchar('\n');}
template<typename T, typename... U>
void print(T head, U... tail) {
    cout << head << " ";
    print(tail...);
}

const int MOD = 1000000007;
#define MAX_N 100005
LL cnt[2][MAX_N];

int main()
{
    int n, p;
    RI(n, p);
    REP(i, n) {
        int a;
        RI(a);
        if(i == 0) {
            if(a % 2 == 0) {
                cnt[0][0] = 2;
                cnt[1][0] = 0;
            } else {
                cnt[0][0] = 1;
                cnt[1][0] = 1;
            }
        } else {
            if(a % 2 == 0) {
                cnt[0][i] = cnt[0][i-1] * 2;
                cnt[1][i] = cnt[1][i-1] * 2;
            } else {
                cnt[0][i] = cnt[0][i-1] + cnt[1][i-1];
                cnt[1][i] = cnt[0][i-1] + cnt[1][i-1];
            }
        }
    }
    printf("%lld\n", cnt[p][n-1]);
    return 0;
}


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

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        int[] A = new int[N];
        int[] B = new int[N];
        int[] C = new int[N-1];
        for (int i = 0; i < N; i++) {
            A[i] = scan.nextInt();
        }
        for (int i = 0; i < N; i++) {
            B[i] = scan.nextInt();
        }
        for (int i = 0; i < N-1; i++) {
            C[i] = scan.nextInt();
        }
        int answer = B[A[0]-1];
        for (int i = 1; i < N; i++) {
            answer += B[A[i]-1];
            if (A[i-1] + 1 == A[i]) {
                answer += C[A[i-1]-1];
            }
        }
        System.out.println(answer);
    }
}


Measured memory_bytes: 21844
#include<cstdio>
#include<algorithm>
#include<iostream>

using namespace std;

#define B cerr<<"Break Point"<<endl;

constexpr int N=15;
constexpr int M=105;

int n,m;
int d[N][N];
int f[M][M];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d",&d[i][j]);
    for(int i=0;i<=100;++i)
        for(int j=0;j<=100;++j)
            for(int x=1;x<=n;++x)
                for(int y=1;y<=m;++y)
                    f[i][j]=max(f[i][j],d[x][y]-i*x-j*y);
    for(int x=1;x<=n;++x)
        for(int y=1;y<=m;++y)
        {
            int nowdis=1e9;
            for(int i=0;i<=100;++i)
                for(int j=0;j<=100;++j)
                    nowdis=min(nowdis,f[i][j]+i*x+j*y);
            if(nowdis!=d[x][y])
            {
                printf("Impossible");
                return 0;
            }
        }
    printf("Possible\n");
    printf("%d %d\n",202,10401);
    for(int i=1;i<=100;++i) printf("%d %d X\n",i,i+1);
    for(int i=102;i<=201;++i) printf("%d %d Y\n",i,i+1);
    for(int i=0;i<=100;++i)
        for(int j=0;j<=100;++j)
            printf("%d %d %d\n",i+1,202-j,f[i][j]);
    printf("%d %d\n",1,202);
    return 0;
}


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

vector<int> split(string s) {
	s += 'T';
	vector<int> r;
	for (int i = 0; i < s.size(); i++) {
		int j = i;
		for (; j < s.size() && s[j] == 'F'; j++) {
			
		}
		r.emplace_back(j - i);
		i = j;
	}
	return r;
}

int main() {
	string s;
	pair<int, int> goal;
	cin >> s >> goal.first >> goal.second;
	auto v = split(s);
	goal.first -= v[0];
	vector<int> puni, muni;
	for (int i = 1; i < v.size(); i++) {
		(i % 2 ? muni : puni).emplace_back(v[i]);
	}
	set<int> x, y;
	x.emplace(0);
	y.emplace(0);
	for (auto &i : puni) {
		set<int> next;
		for (auto &j : x) {
			next.emplace(j + i);
			next.emplace(j - i);
		}
		swap(x, next);
	}
	for (auto &i : muni) {
		set<int> next;
		for (auto &j : y) {
			next.emplace(j + i);
			next.emplace(j - i);
		}
		swap(y, next);
	}
	cout << (x.find(goal.first) != x.end() && y.find(goal.second) != y.end() ? "Yes" : "No") << endl;
	return 0;
}

Measured memory_bytes: 768
using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.AccessControl;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = ReadLineInt();
            var a = ReadLineStringSplit().ToList();

            var q = a.Distinct().Count();
            var e = a.Count()-q;

            Console.WriteLine((e <= 0) ? "YES" : "NO");
            ReadLine();
        }

        //メモ

        //配列
            //降順
            //var sort = array.OrderBy(x => -x).ToArray();

            //合計値
            //array.Sum();

        //kのn乗
        //(int) Math.Pow(k, n);

        //for文の逆
        //for(int i = array.Length - 1; i >= 0; i--) { }


        //最大公約数
        static int gcd(int a, int b)
        {
            if (a > b) {
                return gcd(b, a);
            }

            while (b != 0) {
                var remainder = a % b;
                a = b;
                b = remainder;
            }

            return a;
        }

        //最小公倍数
        static int lcm(int a, int b) => a * b / gcd(a, b);

        /// <summary>
        /// コンビネーション
        /// </summary>
        static int nCm(int n, int m)
        {
            if (m == 0) return 1;
            if (n == 0) return 0;
            return n * nCm(n - 1, m - 1) / m;
        }

        public static string ReadLine() => Console.ReadLine();
        public static int ReadLineInt() => int.Parse(Console.ReadLine());
        public static long ReadLineLongInt() => long.Parse(Console.ReadLine());
        public static string[] ReadLineStringSplit(char a = ' ') => ReadLine().Split(a).ToArray();
        public static int[] ReadLineIntSpilit(char a = ' ') => ReadLine().Split(a).Select(x => int.Parse(x)).ToArray();
        public static long[] ReadLineLongSpilit(char a = ' ') => ReadLine().Split(a).Select(x => long.Parse(x)).ToArray();
        static string[] GetAlphaLowerArray() => new string[] { "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" };
        static string[] GetAlphaUpperArray() => new string[] { "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" };
    }
}


Measured memory_bytes: 44232
// ※※※ 解答不能 ※※※
// kort0n氏.
// https://atcoder.jp/contests/abc142/submissions/7731316
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

int N, M;
int a[1050], b[1050], c[1050][20];

void input() {
    cin >> N >> M;
    for(int i = 1; i <= M; i++) {
        cin >> a[i] >> b[i];
        for(int j = 1; j <= b[i]; j++) cin >> c[i][j];
    }
}

void solve() {
    input();
    const int INF = 1e9;
    vector<int> dp(5000, INF);
    dp[0] = 0;
    for(int item = 1; item <= M; item++) {
        int now = 0;
        for(int j = 1; j <= b[item]; j++) {
            now |= (1 << (c[item][j] - 1));
        }
        for(int bits = 0; bits < (1 << N); bits++) {
            chmin(dp[bits | now], dp[bits] + a[item]);
        }
    }
    if(dp[(1 << N) - 1] == INF) dp[(1 << N) - 1] = -1;
    cout << dp[(1 << N) - 1] << endl;
    return;
}

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


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

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

int main()
{
  int N, x; scanf("%d %d", &N, &x);
  vector<ll> A(N);
  for (int i = 0; i < N; ++i) {
    scanf("%lld", &A[i]);
  }

  ll ans = 0;
  for (int i = 1; i < N; ++i) {
    if (A[i - 1] + A[i] <= x) { continue; }
    ll diff = A[i - 1] + A[i] - x;
    ans += diff;
    A[i] = max(0LL, A[i] - diff);
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
int main(void)
{
  int m,f,r;
  while(1)
  {
  scanf("%d %d %d",&m,&f,&r);
 if (m==-1&&f==-1&&r==-1)
  break;

  else if (m!=-1&&f!=-1&&m+f>=80)
  printf("A\n");
  else if (m!=-1&&f!=-1&&m+f>=65&&m+f<80)
  printf("B\n");
  else if (m!=-1&&f!=-1&&m+f>=50&&m+f<65)
  printf("C\n");
  else if (r>=50)
  printf("C\n");
  else if (m!=-1&&f!=-1&&m+f>=30&&m+f<50)
  printf("D\n");
  else if (m+f<30||m==-1||f==-1)
  printf("F\n");
  }

  return 0;
}

Measured memory_bytes: 584
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
int main()
{
	int n;
	while(~scanf("%d", &n))
	{
		double min = 9999999.0;
		double t, a;
		int index;
		double arr[1010];
		scanf("%lf %lf", &t, &a);
		for(int i = 0;i < n; i++)
		{
			scanf("%lf", &arr[i]);
			double sum = t - arr[i]*0.006;
			if(min > fabs(sum-a))
			{
				index = i;
				min = fabs(sum-a);
			} 
		}
		printf("%d\n", index+1);
	}
	return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <vector>

const int MOD = 1e9 + 7;
const int iINF = 2147483647 / 2;
const long long int llINF = 9223372036854775807 / 2;

using namespace std;
using ll = long long int;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;

typedef pair<ll, ll> pll;
bool paircomp(const pll &a, const pll &b) {
  if (a.first == b.first)
    return a.second < b.second;
  return a.first < b.first;
}

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define RREP(i, n) for (ll i = (n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define AUTO(i, m) for (auto &i : m)
#define ALL(a) (a).begin(), (a).end()
#define MAX(vec) *std::max_element(vec.begin(), vec.end())
#define MIN(vec) *std::min_element(vec.begin(), vec.end())
#define ARGMAX(vec)                                                            \
  std::distance(vec.begin(), std::max_element(vec.begin(), vec.end()))
#define ARGMIN(vec)                                                            \
  std::distance(vec.begin(), std::min_element(vec.begin(), vec.end()))
#define REV(T) greater<T>()
#define PQ(T) priority_queue<T, vector<T>, greater<T>>
#define VVL(a, b, c) vector<vector<ll>>(a, vector<ll>(b, c))
#define VVVL(a, b, c, d)                                                       \
  vector<vector<vector<ll>>>(a, vector<vector<ll>>(b, vector<ll>(c, d)))
#define SP(a) setprecision(a)
#define SQRT(a) sqrt((long double)(a))
#define DPOW(a, b) pow((long double)(a), (long double)(b))
#define UNIQUE(vec)                                                            \
  do {                                                                         \
    sort(ALL((vec)));                                                          \
    (vec).erase(std::unique(ALL((vec))), (vec).end());                         \
  } while (0)

ll POW(ll n, ll m) {
  if (m == 0) {
    return 1;
  } else if (m % 2 == 0) {
    ll tmp = POW(n, m / 2);
    return (tmp * tmp);
  } else {
    return (n * POW(n, m - 1));
  }
}

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll A, B;
  cin >> A >> B;
  A += B;
  if (A % 2 == 1)
    cout << "IMPOSSIBLE" << endl;
  else
    cout << A / 2 << endl;
  return 0;
}


Measured memory_bytes: 256
// #include <bits/stdc++.h>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<set>
#define rep(i,n) for(int i=0;i<n;i++)
#define exf(x)	 for(auto&& tmp : x) { cout << tmp << endl; }	// 拡張for
#define testP	 cout << "------------------ test ------------------" << endl;	// 動作確認テスト
#define testX(x) cout << "testout : " << x << endl;	// テストアウト
typedef long long ll;
using namespace std;
const int MOD{ int(1e9 + 7) };	// int 1000000007
const int inf{ int(1e9) };	// inf = 1000000000

// ------------------ ベクター表示 ------------------ //
void printVec(vector<ll>& vec) {
	cout << "";
	for (auto it = vec.begin(); it != vec.end(); it++) cout << *it << " ";
	cout << endl;
}

// ------------------ ベクター合計 ------------------ //
int sumVec(vector<int> v) {
	int sum = 0;
	for (size_t i = 0; i < v.size(); i++) sum += v[i];
	return sum;
}

// ------------------ int -> Vector 変換 ------------------ //
vector<int> ItoVec(int x) {

	vector<int> xVec;

	while (x > 0) {
		int tmp = x % 10;
		xVec.insert(xVec.begin(), tmp);
		x /= 10;
	}

	return xVec;
}

// ------------------ 最大公約数関数 ------------------ //
int GCD(int x, int y) {
	if (x == 0) return y;
	else GCD(y % x, x);
}


// -------------------------------------------------- //
// ------------------ ここから本編 ------------------ //
// -------------------------------------------------- //


int A[12][12];

int main(void) {

	int N, M, X;
	cin >> N >> M >> X;

	vector<int> C(N);
	rep(i, N) {
		cin >> C[i];
		rep(j, M) {
			cin >> A[i][j];
		}
	}

	int ans = inf;

	rep(s, 1 << N) {
		int cost = 0;
		vector<int> ck(M);
		rep(i, N) {
			if (s >> i & 1) {
				cost += C[i];
				rep(j, M) ck[j] += A[i][j];
			}
		}
		bool ok = true;
		rep(j, M) if (ck[j] < X) ok = false;
		if (ok) ans = min(ans, cost);
	}

	cout << (ans == inf ? -1 : ans) << endl;

	return 0;
}


Measured memory_bytes: 3632
def resolve():
    MOD = 10 ** 9 + 7
    N = int(input())

    ans = pow(10, N, MOD)
    ans -= pow(9, N, MOD)
    ans -= pow(9, N, MOD)
    ans += pow(8, N, MOD)

    print(ans % MOD)


if __name__ == "__main__":
    resolve()


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

Measured memory_bytes: 3588
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <map>
#include <list>
#include <stdio.h>
#include <sstream>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define all(x) (x).begin(), (x).end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
//ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
//ll lcm(ll x, ll y) {return x / gcd(x, y) * y;}
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const ll mod = 1e9 + 7;
const ll inf = 1LL << 60;
const long double pi = 3.14159265358979323846;

// ****************************************CODE***************************************//

string s,t;
ll dp[3100][3100];

int main() {
    cin >> s >> t;

    for(int i = 0; i < s.size(); i++){
        for(int j = 0; j < t.size(); j++){
            if(s[i] == t[j]) dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + 1);
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j]); 
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1]);
        }
    }

    ll i = s.size(), j = t.size();
    string ans = "";
    while(i > 0 && j > 0){

        if(dp[i-1][j] == dp[i][j]) {
            i--;
        }

        else if(dp[i][j-1] == dp[i][j]) {
            j--;
        }

        else {
            ans = s[i-1] + ans;
            i--;
            j--;
        }
    }

    cout << ans << endl;;
}

Measured memory_bytes: 73984
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  int r,D,x;
  cin >> r >> D >> x;
  vector<int> X(11);
  X[0] = x;
  for(int i=1;i<11;i++)
  {
    X[i] = r*X[i-1] - D;
    cout << X[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    string s;
    cin>>s;
    
    int ct=0;
    for(int i=0;i<3;i++){
        if(s[i]=='o') ct++;
    }
    
    cout<<700 + ct*100 <<endl;
}


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

using namespace std;

int main(){
    int n,x,max = 0,sum = 0;
    cin >> n;
    vector<int>v(n);

    for(int i = 0;i < n;i++){
        cin >> v[i];
        if(max <= v[i]){
            max = v[i];
            x = i;
        }
    }

    for(int i = 0;i < n;i++){
        if(x == i)sum += v[i]/2;
        else sum += v[i];
    }

    cout << sum << endl;


    return 0;
}

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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define POSSIBLE cout << ((n) ? "POSSIBLE\n" : "IMPOSSIBLE\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int32 n,t;
    cin >> n >> t;
    vector<pii> ab(n);
    REP(i,n)cin >> ab[i].first >> ab[i].second;
    vector<vector<int32>> dp1(n+1,vector<int32>(t,0)), dp2(n+2,vector<int32>(t,0));
    REP(i,n){
        FORR(j,t-1,0){
            dp1[i+1][j] = dp1[i][j];
            if(j-ab[i].first < 0)continue;
            dp1[i+1][j] = max(dp1[i+1][j], dp1[i][j-ab[i].first] + ab[i].second);
        }
    }
    FORR(i,n-1,0){
        FORR(j,t-1,0){
            dp2[i+1][j] = dp2[i+2][j];
            if(j-ab[i].first < 0)continue;
            dp2[i+1][j] = max(dp2[i+1][j], dp2[i+2][j-ab[i].first] + ab[i].second);
        }
    }
    int32 ans = 0;
    FOR(i,1,n+1){
        REP(j,t){
            // cout << i << " " << j << " " << dp1[i-1][t-1-j] << " " << dp2[i+1][j] << " " << ab[i-1].second << " " << dp1[i-1][t-1-j] + dp2[i+1][j] + ab[i-1].second << endl;
            ans = max(ans, dp1[i-1][t-1-j] + dp2[i+1][j] + ab[i-1].second);
        }
    }
    ANS(ans);
    return 0;
}

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

#define ll long long
using namespace std;

const int _M=1e5+40;

ll a[_M],t[_M],ans[_M],k=0;

struct
{
    int x,y;
} e[_M];

int fd(int x)
{
    return x==a[x]?x:a[x]=fd(a[x]);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)a[i]=i,t[i]=1;
    for(int i=1; i<=m; i++)
        scanf("%d%d",&e[i].x,&e[i].y);
    ll an=(ll)n*(ll)(n-1)/2;
    ans[k++]=an;
    // cout<<an<<endl;
    for(int i=m; i>=1; i--)
    {
        int ra=fd(e[i].x),rb=fd(e[i].y);
        if(ra!=rb)
        {
            an-=((ll)t[ra]*(ll)t[rb]);
            t[ra]+=t[rb];
            a[rb]=ra;
        }
        ans[k++]=an;
    }
    k-=2;
    while(k>=0)
        cout<<ans[k--]<<endl;
    return 0;
}






Measured memory_bytes: 4480
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <random>
using namespace std;

#define ll long long
#define rep(i, n) for(ll i = 0; i < (n); i++)
ll MOD = 1e9 + 7;
int INF = 1 << 30;
ll INFL = 1LL << 60;

int main() {
  int a,b;
  cin >> a >>b;
  if(a > 0 && a < 10 && b > 0 && b < 10){
    cout << a*b <<endl;
  }
  else{
    cout << -1 <<endl;
  }
}


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

int main() {
	int ans = 0, sum;
	size_t N;
	cin >> N;
	vector<int> A1(N), A2(N);
	for (auto &x : A1) cin >> x;
	for (auto &x : A2) cin >> x;
	for (size_t i = 1; i < N; ++i) A1[i] += A1[i - 1];
	for (size_t i = 1; i < N; ++i) A2[i] += A2[i - 1];
	for (size_t i = 0; i < N; ++i) {
		sum = A1[i];
		if (i == 0) sum += A2[N - 1];
		else sum += A2[N - 1] - A2[i - 1];
		ans = max(ans, sum);
	}
	cout << ans;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)


def dfs(v, c, C, visited, G):
    visited[v] = True
    C[v] = c

    for nv, w in G[v]:
        if visited[nv]:
            continue
        dfs(nv, c^w, C, visited, G)


def main():
    N = int(input())
    
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        G[u-1].append([v-1, w%2])
        G[v-1].append([u-1, w%2])
    # print(G)

    C = [0]*N
    visited = [False]*N
    dfs(0, 0, C, visited, G)
    for c in C:
        print(c)
    
        


if __name__ == '__main__':
    main()

Measured memory_bytes: 83676
using System;

namespace ABC063Ax
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b;

            var word = Console.ReadLine().Split(' ');
            a = int.Parse(word[0]);
            b = int.Parse(word[1]);

            if (a + b < 10)
                Console.WriteLine(a + b);
            if (a + b >= 10 || a+b==10)
                Console.WriteLine("error");

            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 11092
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
#include <queue>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=101000;
int n,a[N];
ll ret;
int main() {
	scanf("%d",&n);
	rep(i,1,n+1) {
		scanf("%d",a+i);
		if (a[i]&&a[i-1]) --a[i],++ret;
		ret+=a[i]/2;
		a[i]%=2;
	}
	printf("%lld\n",ret);
}

Measured memory_bytes: 512
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
#include <iomanip>
#include<queue>
#include<algorithm>
#include <functional>
#include<vector>
#include <math.h>
#include <numeric>
#include <stack>
#include <map>
using namespace std;
#define DEBUG 0

int main() {
	int N; cin >> N;
	string str = "";
	while (N != 0) {
		int r = N % 2;
		if (r < 0) r += 2;

		N = (N - r) / (-2);
		str += (char)('0' + r);
	}
	reverse(str.begin(), str.end());
	if (str == "") str = "0";
	cout << str << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		double r = sc.nextDouble();
		double pi = Math.PI;
		double area = r * r * pi;
		double length = 2 * r * pi;
		System.out.printf("%f %f", area, length);
		sc.close();
	}
}



Measured memory_bytes: 28228
#include<bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int K;
  string S;
  cin>>K;
  cin>>S;
  if(S.size() > K){
    for(int i = 0;i < K;i++){
      cout<<S[i];
    }
    cout<<"..."<<'\n';
  }else if(S.size() <= K){
    cout<<S<<'\n';
  }
}

Measured memory_bytes: 3620
#pragma region header
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cctype>
#include <assert.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>
#include <cstring>
#include <array>
// ===============================================================
//using系
#pragma region header
using namespace std;
using lint = long long;
using ld = long double;
using ulint = unsigned long long;
const int dx[] = { 1,0,-1,0 };
const int dy[] = { 0,1,0,-1 };
constexpr lint mod = 1000000007;
constexpr long double pi = 3.141592653589793238462643383279;
#pragma endregion
// ========================================================================
//define
#define INF (lint)10000000000000000;
#define mod (int)1000000007
#pragma region header
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
#pragma endregion
#pragma endregion



int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	long long k, a, b; cin >> k >> a >> b;
	if (b - a <= 2) cout << k + 1 << endl;
	else {
		cout << a + (b - a) * ((k - a + 1) / 2) + (k - a + 1) % 2 << endl;
	}

	return 0;
}

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

int lcs[3009][3009];
string a, b, ans;

int call(int i, int j)
{
    if(i == a.size() || j == b.size())
        return 0;
    if(lcs[i][j] != -1)
        return lcs[i][j];

    if(a[i] == b[j])
        return lcs[i][j] = 1 + call(i+1, j+1);
    else
        return lcs[i][j] = max(call(i+1, j), call(i, j+1));
}

string call2(int i, int j)
{
    if(i == a.size() || j == b.size())
        return "";
    if(a[i] == b[j])
        return a[i] + call2(i+1, j+1);
    else if(lcs[i+1][j] >= lcs[i][j+1])
        return call2(i+1, j);
    else
        return call2(i, j+1);
}

int main()
{
    cin >> a >> b;
    memset(lcs, -1, sizeof lcs);
    call(0, 0);
    cout << call2(0, 0);
}


Measured memory_bytes: 36224
#include <bits/stdc++.h>
using namespace std;
long long x=1;
bool yes=true;
int N;
long long a;

int main(){
   cin >> N;
   a=1e9+7;
   for(int i=1;i<=N;i++)
   {
       x=(x*i)%a;
   }
   
   printf("%lld",x);
}
    
    
    

  

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

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5 + 1;

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

  CIN(N);
  vector< int > A(N);
  REP(i, N)
    cin >> A[i];

  ll ans = 0ll;
  int ub = 0;
  ll sm = 0ll;
  REP(lb, N) {
    while (ub < N && (sm + A[ub]) == (sm xor A[ub])) {
      sm += A[ub++];
    }
    ans += ub - lb;
    /*
    debug(ans);
    debug(lb);
    debug(ub);
    debug(sm);
    cout << endl;
    */
    sm -= A[lb];
    if (lb == ub) ub++;
  }
  cout << ans << endl;

  return 0;
}



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

int main() {
  int n,m;
  cin>>n>>m;
  int L=-1,R=1000001,ans;
  
  for(int i;i<m;i++){
    int l,r;
    cin>>l>>r;
    L=max(L,l);
    R=min(R,r);
  }
  
  ans=max(R-L+1,0);
  
  cout<<ans<<endl;
}


Measured memory_bytes: 3604
#include <iostream>
#include <vector>
#include <cstring>
#include <bits/stdc++.h>

using namespace std;


int main() {
    int n;
    scanf("%d", &n);
    long long ans = n;
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x > y) swap(x, y);
        ans -= 1LL * x * (n - y + 1);
        ans += 1LL * i * (n - i + 1);
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 3796
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
public class Main {
	public static void main(String[] args)throws IOException {
		FastReader sc = new FastReader();
		PrintWriter pw = new PrintWriter(System.out);
		int a = sc.nextInt();
		System.out.println(a + a * a + a * a * a);

	}
}





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;
	}
}

Measured memory_bytes: 32784
// Problem : B - Minesweeper
// Contest : AtCoder - AtCoder Beginner Contest 075
// URL : https://atcoder.jp/contests/abc075/tasks/abc075_b
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define eb emplace_back
#define pb push_back
#define size(s) (int)s.size()
#define int long long
#define vi vector<int>
#define vs vector<string>
#define vv vector<vector<int>>
#define pii pair<int,int>
#define m_p(x,y) make_pair(x,y)
#define vp vector<pair<int,int>>
#define setbits(x) __builtin_popcountll(x)
#define f first
#define se second
#define inc(v,n,x) v.assign(n,x)
#define incd(v,n) v.resize(n)
#define iniz(n) memset(n,0,sizeof(n))
#define inin(n) memset(n,-1,sizeof(n))
#define inimi(n) memset(n,0xc0,sizeof(n))
#define inima(n) memset(n,0x3f,sizeof(n))
#define all(v) (v).begin(),(v).end()

using namespace std;

template<typename T1,typename T2>istream &operator>>(istream &is, vector<pair<T1,T2>> &v) { for (pair<T1,T2> &t : v) is >> t.f>>t.se; return is; }
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

const int N=200001;
double pi=acos(-1.0);
int md=1e9+7;
const int INF=1e15;
int dx1[]={0,0,-1,1,1,1,-1,-1};
int dy1[]={1,-1,0,0,1,-1,1,-1};

template<class T>
T abst(T a)
{return a<0?-a:a;}

template<class T>
T max2(T a,T b){return a>b?a:b;}
template<class T>
T min2(T a,T b){return a<b?a:b;}

void solve()
{
	int n,m;cin>>n>>m;
	vs v(n);cin>>v;
	int ans[n][m];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			char c=v[i][j];
			if(c=='.')
			{
				int cnt=0;
				for(int k=0;k<8;k++)
				{
					int x=i+dx1[k];
					int y=j+dy1[k];
					if(x>=0 and x<n and y>=0 and y<m and v[x][y]=='#')
					cnt++;
				}
				ans[i][j]=cnt;
			}
			else
			ans[i][j]=-1;
		}
	}
	for(int i=0;i<n;i++){
	for(int j=0;j<m;j++)
	if(ans[i][j]==-1)
	cout<<"#";
	else
	cout<<ans[i][j];
	cout<<"\n";}
}

int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)
{
    solve();
}
return 0;
}


Measured memory_bytes: 3612
#include<iostream>
using namespace std;
const int N=100100;
const long long P=(int)1e9+7;
long long fa[N],in[N],n,d,f[N];
long long pow(long long n,long long k,long long p)
{
    long long ans=1;
    while(k)
    {
        if(k&1) ans=ans*n%p;
        n=n*n%p;
        k>>=1;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    ++n;
    fa[0]=1;
    for(int i=1;i<=n;++i)
        fa[i]=fa[i-1]*i%P;
    in[0]=1;
    for(int i=1;i<=n;++i)
        in[i]=pow(fa[i],P-2,P);
    for(int i=1;i<=n;++i)
    {
        int t;
        cin>>t;
        if(f[t]) d=i-f[t]+1;
        else f[t]=i;
    }
    for(int i=1;i<=n;++i)
    {
        long long ans;
        ans=fa[n]*in[i]%P*in[n-i];
        if(n-d-i+1>=0)
            ans-=fa[n-d]*in[i-1]%P*in[n-d-i+1];
        ans=(ans%P+P)%P;
        cout<<ans<<endl;
    }
    return 0;
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<string> A(N);
  REP(i, N) cin >> A[i];
  vector<string> B(M);
  REP(i, M) cin >> B[i];
  bool ans = false;
  for(int i = 0; i < N - M + 1; i++) {
    for(int j = 0; j < N - M + 1; j++) {

      bool flag = true;
      for(int bx = 0; bx < M; bx++) {
        for(int by = 0; by < M; by++) {
          int ax = i + bx;
          int ay = j + by;
          if(A[ax][ay] != B[bx][by]) { flag = false; }
        }
      }

      if(flag) { ans = true; }
    }
  }
  if(ans) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int A, B, C;
    cin >> A >> B >> C;
    if ((100 * A + 10 * B + C) % 4 == 0)
        cout << "YES\n";
    else
        cout << "NO\n";
}

Measured memory_bytes: 256
import sys
s=input()
if s[0]!="A":
	print("WA")
	sys.exit()

count=0
for i in range(2,len(s[2:])+1):
	if s[i]=='C':
		count+=1
		c=i
if count!=1:
	print("WA")
	sys.exit()
s=s.replace(s[c],'')
s=s.replace(s[0],'')
if not s.islower():
	print("WA")
	sys.exit()

print("AC")

Measured memory_bytes: 3064
#include<iostream>
#pragma GCC optimize ("Ofast")
#define PB push_back
#define MP make_pair
#define ll long long
#define ull unsigned long long 
#define pii pair<int,int>
#define all(X) (X).begin(),(X).end()
#define F first
#define S second
#define endl cout<<'\n';
#define __IO ios::sync_with_stdio(false),cin.tie(0);
using namespace std;

const int mod = 1e9+7;
char m[1001][1001];
int dp[1001][1001] , h , w;
void init(){
	dp[0][0] = 1;
	for(int i=1 ; i<h ; ++i){
		if(m[i][0] == '.' && m[i-1][0] == '.') dp[i][0] = dp[i-1][0];
	}
	for(int i=1 ; i<w ; ++i){
		if(m[0][i] == '.' && m[0][i-1] == '.') dp[0][i] = dp[0][i-1];
	}
}
int main(){
__IO
	cin >> h >> w;
	for(int i=0 ; i<h  ; ++i)
		for(int j=0 ; j<w ; ++j)
			cin >> m[i][j];
	init();
	for(int i=1 ; i<h ; ++i)
		for(int j=1 ; j<w ; ++j){
			if(m[i-1][j] == '.') dp[i][j] += dp[i-1][j] , dp[i][j] %= mod;
			if(m[i][j-1] == '.') dp[i][j] += dp[i][j-1] , dp[i][j] %= mod;
		}
	cout << dp[h-1][w-1]%mod <<'\n';
}

Measured memory_bytes: 5120
#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#include <deque>
#include <queue>
#include <set>

using namespace std;

vector<int> g[100000];

int main(){
  const int n = getInt();
  const int m = getInt();

  REP(i,m){
    const int a = getInt() - 1;
    const int b = getInt() - 1;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  vector<int> use(n);
  deque<int> ans;

  REP(i,2){
    int cur = 0;
    use[cur] = 0;

    while(true){
      use[cur] = 1;
      if(i == 0) ans.push_back(cur);
      else if(cur != 0) ans.push_front(cur);

      REP(i,g[cur].size()){
        const int next = g[cur][i];
        if(use[next] == 0) {
          cur = next;
          break;
        }
      }

      if(use[cur] == 1) break;
    }
  }

  printf("%d\n", (int)ans.size());
  REP(i,ans.size())
    printf("%d%c", ans[i] + 1, i == (int)ans.size() - 1 ? '\n' : ' ');

  return 0;
}


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

int main() {
    int N;
    cin >> N;
    int max_num = (int)sqrt((double)N);
    int ans = 0;
    for (int i = 1; i <= max_num + 1; i++) {
        if (ans < i * i && i * i <= N) ans = i * i;
    }
    cout << ans << endl;
    return 0;
}

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

#define    ll     long long int

int ara1[111];
int ara2[111];

int main( )
{
    int n, i, j, k;
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> ara1[i];
    }
    for (i = 1; i <= n; i++) {
        cin >> ara2[i];
    }
    for (i = 2; i <= n; i++) {
        ara1[i] += ara1[i - 1];
    }
    for (i = n - 1; i >= 1; i--) {
        ara2[i] += ara2[i + 1];
    }
    int mx = 0;
    for (i = 1; i <= n; i++) {
        mx = max(mx, ara1[i] + ara2[i]);
    }
    cout << mx << '\n';
    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>
int a[249];

int p(int i){return i/2;}
int l(int i){return i*2;}
int r(int i){return i*2+1;}

int main(){
  
  int n,i;
  scanf("%d",&n);
  for(i=1;i<=n;i++)scanf("%d",&a[i]);
  for(i=1;i<=n;i++){
    printf("node %d: key = %d, ",i,a[i]);

    if(p(i)>=1)printf("parent key = %d, ",a[p(i)]);
    if(l(i)<=n)printf("left key = %d, ",a[l(i)]);
    if(r(i)<=n)printf("right key = %d, ",a[r(i)]);
    printf("\n");
  }
  return 0;
}



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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,K;
int T[111111],D[111111];

bool ex[111111];

signed main(){
    cin>>N>>K;
    rep(i,N)cin>>T[i]>>D[i];

    vector<pint>vs;
    rep(i,N)vs.pb(pint(D[i],i));
    sort(all(vs));reverse(all(vs));

    int ans=0;
    int num=0,sum=0;
    priority_queue<int,vint,greater<int>>que;
    for(int i=0;i<N;i++){
        int k=vs[i].se;
        if(i<K){
            sum+=D[k];
            if(!ex[T[k]]){
                ex[T[k]]=true;
                num++;
            }
            else{
                que.push(D[k]);
            }
        }
        else if(!ex[T[k]]&&que.size()){
            sum-=que.top();
            que.pop();
            ex[T[k]]=true;
            num++;
            sum+=D[k];
        }
        chmax(ans,num*num+sum);
    }
    cout<<ans<<endl;
    return 0;
}


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

int main() {
  int N; //支払う金額
  int A; //所持している1円玉の枚数
  
  cin >> N;
  cin >> A;
  
  int B = N / 500; //500円玉を何枚使うか
  int C = N - B * 500; //1円で払う金額
    
  if (C <= A){
  	cout << "Yes" << endl;
  }else{
  	cout << "No" << endl;
  }
}


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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

struct Edge { ll from, to; ld weight; };
typedef std::vector<Edge> Edges;
typedef std::vector<Edges> Graph;
typedef std::pair<long long, int> P;


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m, p, a, b;
	while (cin >> n >> m >> p >> a >> b, n) {
		vi t(n); REP(i, n)cin >> t[i];
		a--; b--;
		vector<vector<ld>> d(m, vector<ld>(m, INF*INF));
		vector<Edge> e(p);
		REP(i, p) {
			int a, b;
			ld c;
			cin >> a >> b >> c;
			a--; b--;
			e[i] = { a,b,c };
		}
		Graph g((1 << n)*m);
		REP(i, p) {
			REP(j, 1 << n) {
				REP(k, n) {
					if (j&(1 << k)) {
						g[(1 << n)*e[i].from + j].push_back(Edge{ (1 << n)*e[i].from + j,(1 << n)*e[i].to + (j ^ (1 << k)),e[i].weight / t[k] });
						g[(1 << n)*e[i].to + j].push_back(Edge{ (1 << n)*e[i].to + j,(1 << n)*e[i].from+ (j ^ (1 << k)),e[i].weight / t[k] });
					}
				}
			}
		}
		priority_queue < pair<ld, int>, vector < pair<ld, int>>, greater<>> q;
		q.push({ 0,a*(1 << n) + (1 << n) - 1 });
		vector<ld> res((1 << n)*m, INF*INF);
		res[a*(1 << n) +(1<<n)-1] = 0;
		while (!q.empty()) {
			auto p = q.top(); q.pop();
			int j = p.second;
			ld dist = p.first;
			if (p.first > res[j] + EPS)continue;
			for (auto e : g[j]) {
				if (dist + e.weight < res[e.to]) {
					res[e.to] = dist + e.weight;
					q.push({ res[e.to],e.to });
				}
			}
		}
		ld ans = INF * INF;
		REP(i, 1 << n) {
			ans = min(ans, res[(1 << n)*b + i]);
		}
		if (ans == INF * INF)cout << "Impossible" << endl;
		else cout << fixed << setprecision(12) << ans << endl;
	}
}


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

const ll mod = 1000000007;

int main() {
  ll n;
  cin >> n;
  vector<string> s(2);
  rep(i, 2) cin >> s[i];

  ll ans = 3;
  int si = 0;
  if (n > 1 && s[0][0] == s[0][1]) ans *= 2, si++;
  for (int i = si; i < n - 1; i++) {
    if (s[0][i] == s[1][i]) {
      ans = ans * 2 % mod;
      if (s[0][i + 1] != s[1][i + 1]) i++;
    } else {
      if (s[0][i + 1] != s[1][i + 1]) {
        ans = ans * 3 % mod;
        i++;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"
*/

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

int main()
{
    int x, y;
    cin >> x >> y;
    cout << gcd(x, y) << endl;
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
#define ll long long int
#define FF first
#define SS second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define pss printf
#define MOD 1000000007
#define INF 1e18
#define eps 0.00001
#define endl '\n'
#define debug(n1) cout<<n1<<endl
const int N = 1e5;  // limit for array size
ll n;  // array size

/*template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}
*/
int main(){
	ll n;cin>>n;
	
	cout<<(n*(n-1))/2<<endl;
	
	return 0;
	
}

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

using namespace std;

#define lli long long int
#define REP(i,n) for(int i=0;i<n;i++)
#define DEBUG 1

int main(){

	map<lli,lli> data;
	set<lli>     s;

	lli n;
	cin>>n;
	REP(i,n){
		lli tmp;
		cin>>tmp;
		data[tmp]++;
		s.insert(tmp);
	}
	lli ans=0;

	for(auto itr = s.begin();itr != s.end();itr++){
		lli num = data[*itr];
		lli index = *itr;
		if(num > index){
			ans+=num-index;
		}
		else if(num < index){
			ans += num;
		}
		else{/*num == Index*/
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 11520
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define P 1000000007
#define inf 1e18
int main()
{

    ll i, j;
    string s;
    ll n;
    cin >> n;
    cin >> s;
    ll ans = 0;
    map<char, ll> m1, m2;
    for (i = 1; i < n - 1; i++)
    {
        string t1 = s.substr(0, i);
        string t2 = s.substr(i, n - i);
               
        for (j = 0; j < t1.length(); j++)
        {
            m1[t1[j]]++;
        }
        for (j = 0; j < t2.length(); j++)
        {
            m2[t2[j]]++;
        }
        ll count = 0;
        for (char c = 'a'; c <= 'z'; c++)
        {    //cout<<m1[c]<<" "<<m2[c]<<"\n";
             if(m1[c] * m2[c] != 0)
               count++;
        } 
        ans = max(ans,count);

        m1.clear();
        m2.clear();
    }
    cout << ans << "\n";

    return (0);
}

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

int main(void) {
  string s;
  cin >> s;

  int ans;
  if (s == "SUN") {
    ans = 7;
  } else if (s == "MON") {
    ans = 6;
  } else if (s == "TUE") {
    ans = 5;
  } else if (s == "WED") {
    ans = 4;
  } else if (s == "THU") {
    ans = 3;
  } else if (s == "FRI") {
    ans = 2;
  } else if (s == "SAT") {
    ans = 1;
  }

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

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        String strN = String.valueOf(N);
        String firstPlace = strN.substring(strN.length() - 1);
        String [] hon = {"2", "4", "5", "7", "9"};
        String [] pon = {"0", "1", "6", "8"};

        if (Arrays.stream(hon).anyMatch(str -> firstPlace.equals(str))) {
            System.out.println("hon");
        } else if (Arrays.stream(pon).anyMatch(str -> firstPlace.equals(str))) {
            System.out.println("pon");
        } else {
            System.out.println("bon");
        }

    }
}


Measured memory_bytes: 35768