akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		solver();
	}

	final long MODULO = 1_000_000_000 + 7;

	void solver() {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		long K = sc.nextLong();
		char[][] map = new char[H][W];
		for (int i = 0; i < H; ++i) {
			map[i] = sc.next().toCharArray();
		}

		int a = 0;// 黒マスの個数
		int b = 0;// お互いに横でつながっているペアの数
		int c = 0;// 連結な行の数

		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W; ++j) {
				if (map[i][j] == '#')
					++a;
			}
		}

		for (int i = 0; i < H; ++i) {
			if (map[i][0] == map[i][W - 1] && map[i][0] == '#')
				++c;
		}

		int d = 0;
		for (int i = 0; i < W; ++i) {
			if (map[0][i] == map[H - 1][i] && map[0][i] == '#')
				++d;
		}

		if (c > 0 && d > 0) {
			System.out.println(1);
			return;
		} else if (c == 0 && d == 0) {
			long[][] mx = new long[][] { { a } };
			mx = pow(mx, K - 1);
			System.out.println(mx[0][0]);
			return;
		}

		if (d > 0) {
			map = rev(map);
			c = d;
			d = 0;
			int tmp = H;
			H = W;
			W = tmp;
		}

		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W - 1; ++j) {
				if (map[i][j] == map[i][j + 1] && map[i][j] == '#') {
					++b;
				}
			}
		}

		long[][] mx = new long[][] { { a, -b }, { 0, c } };
		long[][] v = new long[][] { { 1 }, { 1 } };
		mx = pow(mx, K - 1);
		v = mul(mx, v);
		System.out.println(v[0][0]);

	}

	long[][] mul(long[][] a, long[][] b) {
		long[][] ret = new long[a.length][b[0].length];

		for (int i = 0; i < b[0].length; ++i) {
			for (int j = 0; j < a.length; ++j) {
				for (int k = 0; k < a[0].length; ++k) {
					ret[j][i] += a[j][k] * b[k][i] % MODULO;
					ret[j][i] = (ret[j][i] + MODULO) % MODULO;
				}

			}
		}
		return ret;
	}

	long[][] pow(long[][] a, long n) {
		int len = a.length;
		long[][] ret = new long[len][len];
		for (int i = 0; i < len; ++i) {
			ret[i][i] = 1;
		}
		for (; n > 0; n >>= 1, a = mul(a, a)) {
			if (n % 2 == 1)
				ret = mul(a, ret);
		}
		return ret;
	}

	char[][] rev(char[][] map) {
		char[][] ret = new char[map[0].length][map.length];
		for (int i = 0; i < map.length; ++i) {
			for (int j = 0; j < map[0].length; ++j) {
				ret[j][i] = map[i][j];
			}
		}
		return ret;
	}

	void showMap(char[][] map) {
		int H = map.length;
		int W = map[0].length;
		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W; ++j) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

	void tr(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}
}


Measured memory_bytes: 23900
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int n,i;
  cin>>n;
  float a[n],t=0;
  
  for(i=0;i<n;i++)
  { cin>>a[i];
    a[i] = 1/a[i];
   t+=a[i];
  }
 cout<<1/t;
  return 0;
  
}


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

int main()
{
    int N=0,m=0;
    cin>>N;
    m=N;
    int sum=0;
    while(N!=0){
    int a=0;
    a=N%10;
    sum+=a;
    N=N/10;
    }
    int test1=0;
    test1=m%sum;
    if(test1==0){
    cout<<endl<<"Yes";
    }
    else{
    cout<<endl<<"No";
    }
    return 0;
}


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  ll a,b,c,d;
  cin >> a >> b >> c >> d;
  
  ll ans;
  if(a < c)
    ans = max(min(b,d)-c, 0LL);
  else
    ans = max(min(b,d)-a, 0LL);
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstdlib>
#define cinf(n,x,y) for(int i=0;i<(n);i++) cin >> x[i] >> y[i];
typedef long long int ll;
using namespace std;

int main(){
	while(1){
		int n,m,a; cin >>n>>m>>a;
		if(n==0&&m==0&&a==0) break;
		vector<int> h(m),p(m),q(m);
		for(int i=0;i<m;i++){
			cin >> h[i] >> p[i] >> q[i];
		}
		int now=a;
		for(int j=1000;j>0;j--){
			for(int k=0;k<m;k++){
				if(h[k]==j&&p[k]==now) now=q[k];
				else if(h[k]==j&&q[k]==now)now=p[k];
			}
		}
		cout << now << endl;
	}

}


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

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if (a == b && b == c){
        cout << 1 << endl;
    }else if ((a==b&&b!=c) || (a==c&&c!=b) || (b==c&&a!=b)){
        cout << 2 << endl;
    }else{
        cout << 3 << endl;
    }
}

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

int main(){
	int x;
	cin >>x;
	int h=x/3600;
	int m=(x/60)%60;
	int s=x%60;
	cout <<h<<":"<<m<<":"<<s<<endl;

return 0;
}


Measured memory_bytes: 3088
n = int(input())
A = list(map(int, input().split()))

pick_DP = [-float('INF')] * (n//2 + 2)
unpick_DP = [-float('INF')] * (n//2 + 2)
pick_DP[0] = 0
unpick_DP[0] = 0

for i, a in enumerate(A, 1):
    mini = (i-1)//2 - 1
    if mini <= 0:
        mini = 1
    maxi = (i+1)//2

    for num in range(maxi, mini-1, -1):
        if unpick_DP[num] < pick_DP[num]:
            unpick_DP[num] = pick_DP[num]
        pick_DP[num] = max(unpick_DP[num-1] + a, pick_DP[num])

print(max(pick_DP[n//2], unpick_DP[n//2]))

Measured memory_bytes: 31632
#include <bits/stdc++.h>
using namespace std;
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp> 
//using namespace __gnu_pbds; 
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int> >, rb_tree_tag,tree_order_statistics_node_update>
#define standardVar ll n,m,i,j,k,num,num1,num2,flag=0
#define nn <<"\n"
#define __ <<" "<<
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define ittr(x,v) for(auto x=v.begin();x!=v.end();x++)
#define itr(x,n) for(x=0;x<n;x++)
#define itrab(x,a,b) for(x=a;x<b;x++)
#define itpr(v) ittr(x,v)cout<<*x<<" "; cout nn
#define itppr(v) ittr(x,v)cout<<(*x).ff<<" "<<(*x).ss<<"  "; cout nn
#define pi 3.14159265359
#define dTor(x) ((x)*pi)/180.0

typedef long long int ll;       //TYPEDEFS
typedef long double ld;
typedef vector<ll> vl;
typedef map<ll,ll> ml;
typedef set<ll> sl;
typedef string str;
typedef pair<ll, ll> pl;
typedef vector< pl > vpl;
typedef map<pl,ll> mpl;
typedef set< pl > spl;
typedef vector<str> vst;
typedef vector<vl> vvl;

const ll M=1000000007;          //COMMON MODULO
const ll N=998244353;

ll power(ll x, ll y, ll p){     //MODULAR EXPONENTIATION
    ll res=1;
    x=x%p;
    if(x==0)
        return 0;
    while(y>0){
        if(y&1)
            res=(res*x)%p;
        y=y>>1;
        x=(x*x)%p;
    }
    return res;
}
ll inv(ll x, ll m){             //FERMAT INVERSE
    return power(x,m-2,m);
}
struct comp{                    //COMPARISON ON PAIRS
    template<typename T>        
    bool operator()(const T &a, const T &b){
        if (a.ff==b.ff)
            return (a.ss<b.ss);
        else
            return (a.ff<b.ff);
    }
};
bool mod(const pair<ll,ll> &a, const pair<ll,ll> &b){   //COMPARATOR FOR PAIRS (SORTING)
    if(a.ff!=b.ff)
        return (a.ff<b.ff);
    else
        return (a.ss<b.ss);
}
void sieve(vl &prime){          //SIEVE OF ERATOSTHENES
    ll maxN=1e6;
    vector<bool> pr(maxN+1,1);
    for(int i=2;i*i<=maxN;i++)
        if(pr[i]==1)
            for(int j=i*i;j<=maxN;j+=i)
                pr[j]=0;
    for(ll i=2;i<=maxN;i++)
        if(pr[i]==1)
            prime.pb(i);
}
bool isValid(ll i, ll j, ll n, ll m){   //CHECKS FOR OVERFLOW
    if(i>=0&&i<n&&j>=0&&j<m){
        return true;
    }
    return false;
}

//MAIN FUNCTION STARTS HERE

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    standardVar;
    str s;
    str t;
    cin>>s>>t;
    ll c=0;
    itr(i,(ll)s.size()){
        if(s[i]!=t[i]){
            c++;
        }
    }
    cout<<c nn;
    return 0;
}

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

int main() {
	const std::string valid[] = { "dreamer", "dream", "eraser", "erase" };

	std::string s;
	std::cin >> s;

	while (!s.empty()) {
		bool isOK = false;
		for (auto&& v : valid) {
			if (s.size() < v.size())
				continue;

			if (s.substr(s.size() - v.size(), v.size()) == v) {
				s.erase(s.end() - v.size(), s.end());
				isOK = true;
				break;
			}
		}

		if (!isOK) {
			std::cout << "NO" << std::endl;
			return 0;
		}
	}

	std::cout << "YES" << std::endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(ll)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define rep2(i,j,n) for(int j=i;j<n;j++)
#define rep3(i,j,n) for(int j=i;j<=n;j++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define sp(n) cout << fixed << setprecision(n)
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 ll;
using namespace std;
int main(void){
    int n;cin>>n;
    vector<pair<ll,pair<ll,ll>>> p(n);
    rep(i,n){
        ll h,a,b;cin>>a>>b>>h;
        p[i]={h,{a,b}};
    }
    rep(cx,101)rep(cy,101){
        ll H=-1;
        rep(k,n){
            ll x,y,h;
            x=p[k].second.first;
            y=p[k].second.second;
            h=p[k].first;
            if(h==0)continue;
            H=h+abs(x-cx)+abs(y-cy);
            break;
        }
        bool ok=true;
        rep(k,n){
            ll x,y,h;
            x=p[k].second.first;
            y=p[k].second.second;
            h=p[k].first;
            ll th=max(H-abs(x-cx)-abs(y-cy),(ll)0);
            if(th!=h){
                ok=false;
                break;
            }
        }
        if(ok){
            cout<<cx<<" "<<cy<<" "<<H<<endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
/*
                                Shahriar Hasan
                          "University of Chittagong"
                                CSE 18 Batch
*/
#include <bits/stdc++.h>
using namespace std;

#define nln puts("")                    // newline
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))    //max/min from 3 input

#define even(x) x%2==0                  //even odd
#define odd(x) x%2!=0

#define PI acos(-1)                     // constant + math
#define lcm(a,b) (a*b/gcd(a,b))

#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define mp(x,y) make_pair(x,y)          // algorithm habijabi
#define srt(a,n) sort(a,a+n)
#define srtt sort(a.begin(),a.end())
#define cnt(x) count(a,a+n,x)
#define F first
#define S second
#define all(p) p.begin(),p.end()

#define for0(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(ull i=1;i<=n;i++)         //loop
#define forr(i,n) for(int i=n-1;i>=0;i--)
#define mem(a,b) memset(a, b, sizeof(a))
#define fill(a,b) fill(a.begin(),a.end(),b)
#define fill_n(a,n,b) fill_n(a.begin(),n,b)
                        //input
#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define print0(a) for(int i=0;i<a.size();i++)cout<<a[i]<<endl;
#define print1(a) for(int i=1;i<=a.size();i++)cout<<a[i]<<endl;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef set<int> si;
typedef vector<ll> vl;
typedef pair<int,int> pii;           // datatype
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<int>::iterator vit;
typedef set<int>::iterator sit;

///////////////////////////////////////////////////////////
//long long： -9223372036854775808~9223372036854775807
//int： -2147483648~2147483647
//double： -1.7*10^-308~1.7*10^308，15~16位有效数字
//long double： -1.2*10^-4932~1.2*10^4932，18~19位有效数字
///////////////////////////////////////////////////////////


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

ull power(int a,int n)              // to the power
{ll multi=1;for(int i=1;i<=n;i++)multi=multi*a; return multi;}
bool isPrime(ull n)                // prime number check
{if(n==2||n==3)return true;else{ull m=power(2,n-1);if(m%n==1 && n%2==1)return true;else return false;}}
vi getdiv(ll n){vi div;int i;
    for(i=1;i*i<n;i++)
    {if(n%i==0){div.pb(i);div.pb(n/i);}}if(i*i==n)div.pb(i);            // divisor nirnoy kora
    //sort(div.begin(),div.end());
    return div;}
bool isPalindrome(int n){int num=n,sum=0,mod;
    while(n){mod=n%10;n=n/10;sum=sum*10+mod;}
    if(sum==num)return true;else return false;}
////////////////////////////////////////////////////end///////////////////////////////////////////////////////////
////////////////////////////////////////////////////end///////////////////////////////////////////////////////////

int main()
{
    int n;
    cin >> n;
    cout << n*n << endl;
    return 0;
}



Measured memory_bytes: 256
#include <algorithm> //STLͨ���㷨
#include <cmath> //������ѧ����
#include <cstdio> //��������/�������
#include <iostream> //����������/���
#include <cstring> //�ַ�������
#include <string> //�ַ�����
#include <ctime> //�������ʱ��ĺ���
#define itn int
#define fro for
#define ll long long
#define reg register
#define inf 1234567890
#define rep(i,a,b,c) for (int i=a;i<=b;i+=c)
/*#include <bitset> //STLλ������
#include <cstype> //�ַ�����
#include <cerrno> //���������
#include <complex> //������
#include <clocale> //���屾�ػ�����
#include <cstdlib> //������������ڴ���亯��
#include <deque> //STL˫�˶�������
#include <exception> //�쳣������
#include <fstream> //�ļ�����/���
#include <functional> //STL�������㺯��(���������)
#include <limits> //�����������������ֵ����
#include <list> //STL�����б�����
#include <map> //STLӳ������
#include <iomanip> //����������/���
#include <ios> //��������/���֧��
#include <iosfwd> //����/���ϵͳʹ�õ�ǰ������
#include <istream> //����������
#include <ostream> //���������
#include <queue> //STL��������
#include <set> //STL��������
#include <sstream> //�����ַ�������
#include <stack> //STL��ջ����
#include <stdexcept> //��׼�쳣��
#include <streambuf> //�ײ�����/���֧��
#include <utility> //STLͨ��ģ����
#include <vector> //STL��̬��������
#include <cwchar.h>//���ַ�����������/���
#include <cwctype.h> //���ַ�����*/

using namespace std;

int ans;

int max(int x,int y){return x>y?x:y;}

int min(int x,int y){return x<y?x:y;}

int abs(int x){return x>0?x:-x;}

int gcd(int x,int y){return (!y)?x:gcd(y,x%y);}

void exgcd(int a,int b,int &d,int &x,int &y){if (!b){d=a,x=1,y=0;}else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}}

int quick_power(ll a,int b){ll r=1;for (;b;b>>=1,a=a*a)if (b&1) r=r*a;return r;}

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig = false, c = read(); !isdigit(c); c = read()) {
		if (c == '-') iosig = true;
		if (c == -1) return;
	}
	for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
	if (iosig) x = -x;
}

char sr[10000000],z[20];int C=-1,Z=0;
void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(int x){
	if (x<0) sr[++C]='-',x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
//int find(int x){return fa[x]=fa[x]==x?x:find(fa[x]);}

//void add(int x,int y,int z){to[++cnt]=y;v[cnt]=z;Next[cnt]=head[x];head[x]=cnt;}
int main()
{
	int n;read(n);
	if (n%2==1)
	{
		printf("%d\n",(n-1)*(n-3)/2+n-1);
		for (int i=1;i<n;i++)
			printf("%d %d\n",i,n);
		for (int i=1;i<n;i++)
			for (int j=i+1;j<n;j++)
				if (i+j!=n) printf("%d %d\n",i,j);
	}
	if (n%2==0)
	{
		printf("%d\n",n*(n-2)/2);
		for (int i=1;i<=n;i++)
			for (int j=i+1;j<=n;j++)
				if (i+j!=n+1) printf("%d %d\n",i,j);
	}
	return 0;
}









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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		long count[] = new long[N + 1];
		long sum[] = new long[N + 1];
		Arrays.fill(count, 0);
		Arrays.fill(sum, 0);
		int A[] = new int[N];

		for (int i = 0; i < N; i++) {
			int tmp = sc.nextInt();
			A[i] = tmp;
			count[tmp]++;
		}

		long allSum = 0;
		for (int i = 0; i < N + 1; i++) {
			sum[i] = (count[i] * (count[i] - 1)) / 2;
			allSum += sum[i];
		}

		for (int i = 0; i < N; i++) {
			int tmp = A[i];
			long tmp2 = ((count[tmp] - 1) * ((count[tmp] - 1) - 1)) / 2;
			System.out.println(allSum - sum[tmp] + tmp2);
		}
	}
}

Measured memory_bytes: 106504
H,W=map(int,input().split())
A=[]
for i in range(H):
  a=list(input())
  if a != ["."]*W:
    A.append(a)
f = []
for i in range(W):
  flag=1
  for j in range(len(A)):
    if A[j][i]=="#":
      flag=0
      break
  if flag:
    f.append(i)
for i in range(len(A)):
  for j in range(W):
    if j not in f:
      print(A[i][j],end="")
  print()

Measured memory_bytes: 42968
// HTTF.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

#include "bits/stdc++.h"
#define YES "YES"
#define NO "NO"
#define YESNO OUT(three(solve(),YES,NO))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(a);i>=(LL)(b);i--)
#define REP(i,b) FOR(i,zero,b)
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,b,zero)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB push_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define zero 0LL
#define int LL
#define pb emplace_back
#define eb pb

using namespace std;
template<typename T> inline void maximize(T &a, T b) { a = max(a, b); }
template<typename T> inline void minimize(T &a, T b) { a = min(a, b); }
template<typename T> inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template<class T> inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template<class T> inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
typedef long long LL;
typedef double ld;
typedef int ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut, ut> pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef priority_queue<pr, Vpr, greater<pr> > PQ;
inline void outputVI(VI x) { REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }OUT(""); }
const int SIZE1 = 5e5 + 1000;
const int SIZE2 = 2010;
const int SIZE3 = 330;
const int SIZE = SIZE1;
const int MAPSIZE = 40;
const LL p = 7 + 1e9;
const LL INF = 1LL << 60;
const long double EPS = 1e-7;
typedef pair<ld, ut> pld;

#define endl "\n" //インタラクティブでは消す
ut N, M, K, L, Q, D, H, W;
// ut A,B,C,D,E,F,G,H,I,J,O,P,Q,R,T,U;
VI edges[SIZE];
LL vals[SIZE], maps2[SIZE2][SIZE2], answer = zero;
LL maps[SIZE2][SIZE2];
LL DP[101][SIZE];
bool finished[101][SIZE];
LL DP2[SIZE2][SIZE2];
LL DP3[SIZE3][SIZE3][SIZE3];
LL A[SIZE][3];
LL WW[SIZE];
LL VV[SIZE];
LL solve2(LL n,LL w) {
	if (w < 0) return -INF;
	if (finished[n][w]) return DP[n][w];
	if (n== 0) return 0;
	finished[n][w] = true;
	DP[n][w] = max(solve2(n-1,w),solve2(n-1,w-WW[n])+VV[n]);
	return DP[n][w];
}
LL solve() {
	cin >> N >> W;
	EFOR(i, 1,N) {
		cin >> WW[i] >> VV[i];
	}
	cout << solve2(N,W)<<endl;
	return 0;
}




//!!!!!!!!!!!!!!!!!!!実装を詰める!!!!!!!!!!!!!!!!!!!!!!!!!
signed main() {

	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(12);
	solve();
	cin >> N;
	return 0;

}

Measured memory_bytes: 347776
/*
As you do not know the path of the wind,
or how the body is formed in a mother's womb,
so you cannot understand the work of God,
the Maker of all things.
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;

const int N = (int)1e5+5;
int n, col[N];
vector<int> g[N];

void dfs(int u, int p) {
	for (int v : g[u]) if (v != p)
		dfs(v, u);
	if (!col[u]) {
		if (u == 1 || (p && col[p])) {
			puts("First");
			exit(0);
		}
		col[u] = 1, col[p] = 2;
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1, u, v; i < n; ++i) {
		scanf("%d%d", &u, &v);
		g[u].push_back(v), g[v].push_back(u);
	}
	dfs(1, 0);
	puts("Second");
	return 0;
}


Measured memory_bytes: 6144
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

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

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

constexpr double PI = 3.14159265358979323846;
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

class DIncenters {
public:
    void solve(istream& cin, ostream& cout) {
      SPEED;
      ll n, l; cin >> n >> l;
      vector<long double> t(n);
      rep(i, n) {
        cin >> t[i];
      }

      long double sumx = 0;
      long double sumy = 0;

      rep(i, n) {
        for(int j=i+1; j<n; j++) {
          long double k = (t[i]+t[j])/2;
          long double x = cos(2*PI*k/l);
          long double y = sin(2*PI*k/l);
          //debug(i, j, x, y);
          int neg = j-i-1;
          int pos = n-2-neg;
          //debug(pos, neg);
          sumx += x*(pos-neg);
          sumy += y*(pos-neg);
        }
      }

      ll d = n*(n-1)*(n-2)/6;

      cout << setprecision(30) << fixed;
      cout << sumx/d << ' ' << sumy/d << endl;
    }
};

signed main() {
  DIncenters solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int v[101];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>v[i];
}

long s=0;
for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
    s+=(v[i]*v[j]);
    }
}

cout<<s<<'\n';
}


Measured memory_bytes: 256
def dfs(s, n):
    if int(s) > n:
        return 0
    ret = 1 if all(s.count(c) > 0 for c in '357') else 0
    for c in '357':
        ret += dfs(s + c, n)
    return ret


def main():
    from collections import deque
    n = int(input())
    ans = dfs('0', n)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
h, w = map(int, input().split())

if h == 1 or w == 1:
    print(1)
else:
    hc = (w+1) // 2
    hc2 = w // 2
    d, m = divmod(h, 2)
    ans = d * (hc + hc2) + m * hc
    print(ans)


Measured memory_bytes: 2940
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>


/*
 * union-find???????£??????\???????????????
 */
#define ELEMENT_NUM 100000

typedef struct UF{
    int parent;
}UF;

UF uf[ELEMENT_NUM];

/*
 * ?????????idx???parent??¨???????????????????¨??????????
 */
void initialize(int num){
    int i ;
    
    for (i=0; i < num; i++) {
        uf[i].parent = i;
    }
}
/*
 * ??????????±?????????°????????????????????????
 */
int find(int a){
    
    if (a == uf[a].parent) {
        return a;
    }
    
    return uf[a].parent = find(uf[a].parent);
}

int isSame(int a, int b){
    
    if (find(a) == find(b)) {
        return 1;
    }
    else{
        return 0;
    }
}

void unite(int a, int b){
    a = find(a);
    b = find(b);
    
    if (a == b) {
        return;
    }
    
    uf[b].parent = a;
    
}

int main( ){
    
    int n, m, i, u, v, q;
    
    scanf("%d", &n);
    scanf("%d", &m);
    
    initialize(n);
    
    
    for (i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        unite(u, v);
    }
    
    scanf("%d", &q);
    
    
    for (i = 0; i < q; i++) {
        scanf("%d %d", &u, &v);
        if (isSame(u, v)) {
            printf("yes\n");
        }
        else{
            printf("no\n");
        }
    }
    
    return 0;
}

Measured memory_bytes: 972
A = [list(map(int, input().split())) for _ in range(3)]
N = int(input())
B = [int(input()) for _ in range(N)]

result = [[0]*3 for _ in range(3)]

for b in B:
    for i in range(3):
        for j in range(3):
            if b == A[i][j]:
                result[i][j] = 1

for h in result:
    if 0 not in h:
        print("Yes")
        exit()

for i in range(3):
    if result[0][i] == result[1][i] == result[2][i] == 1:
        print("Yes")
        exit()

if result[0][0] == result[1][1] == result[2][2] == 1:
    print("Yes")
    exit()

if result[0][2] == result[1][1] == result [2][0] == 1:
    print("Yes")
    exit()

print("No")

Measured memory_bytes: 3064
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

ll d[110][26];

int main() {
  clr(d,0);
  ll n;
  cin>>n;
  rep(i,0,3){
    string s;
    cin>>s;
    rep(j,0,s.sz){
      d[j][s[j]-'a']++;
    }
  }
  ll ans = 0;
  rep(i,0,n){
    ll mx = 0;
    rep(j,0,26){
      mx = max(mx,d[i][j]);
    }
    if(mx==2)ans++;
    if(mx==1)ans+=2;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <set>

#define INF_LL 9000000000000000000
#define INF 2000000000

#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

class Union_find{
private:
	vector<int> par;
	vector<int> rank;
	int n;

public:
	Union_find(int a){
		n = a;
		for(int i = 0;i < n;i++){
			par.push_back(i);
			rank.push_back(0);
		}
	}

	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;

		if(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}
};


int main(void){
	int n, k;
	while(cin >> n >> k && (n || k)){
		vector<PII> G[101];

		REP(i, k){
			int f;
			cin >> f;
			if(f == 0){
				int a, b;
				cin >> a >> b;
				priority_queue<PII, vector<PII>, greater<PII> > que;
				int d[101];
				fill(d, d+101, INF);
				d[a] = 0;
				que.push(make_pair(0, a));
				while(!que.empty()){
					PII u = que.top(); que.pop();
					int cost = u.first;
					int v = u.second;
					if(d[v] < u.first) continue;
					REP(i, G[v].size()){
						PII e = G[v][i];
						if(d[e.first] > d[v] + e.second){
							d[e.first]  = d[v] + e.second;
							que.push(PII(d[e.first], e.first));
						}
					}
				}
				if(d[b] == INF){
					cout << -1 << endl;
				}else{
					cout << d[b] << endl;
				}
			}else{
				int c, d, e;
				cin >> c >> d >> e;
				G[c].push_back(make_pair(d, e));
				G[d].push_back(make_pair(c, e));
			}
		}
	}
}

Measured memory_bytes: 3040
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
  string x;
  int k;
  cin >> x >> k;
  vector<string> data;
  for (int i = 0; i < x.length(); i++) {
    for (int j = 1; j < x.length() - i + 1 && j <= k; j++) {
      data.push_back(x.substr(i, j));
    }
  }
  sort(data.begin(), data.end());
  unique(data.begin(), data.end());

  cout << data[k-1] << endl;
  return 0;
}


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

int main() {
  string S;
  cin>>S;
  int Y=0,M=0;
  for(int i=0;i<4;i++){
    Y*=10;
    Y+=S[i]-'0';
  }
  for(int i=5;i<7;i++){
    M*=10;
    M+=S[i]-'0';
  }
  if(Y<2019){
    cout<<"Heisei"<<endl;
  }
  else if(M<5&&Y==2019){
    cout<<"Heisei"<<endl;
  }
  else{
    cout<<"TBD"<<endl;
  }
}



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

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[94m%s: " fmt "\n\033[0m", \
    __func__, ##__VA_ARGS__)
#else 
# define _debug(...) ((void) 0)
#endif
#define rep(i, n) for (int i=0; i<(n); i++)
#define Rep(i, n) for (int i=1; i<=(n); i++)
#define range(x) (x).begin(), (x).end()
typedef long long LL;
typedef unsigned long long ULL;

int main() {
  string s;
  cin >> s;
  cout << (int)s.size() - 2 * (int)count(range(s), '-'); 
  return 0;
}



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

using namespace std;

typedef long long ll;

int main(){
    int n;
    double m;
    cin >> n >> m;
    int a[n], uk = 0;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        uk += a[i];
    }
    sort (a, a + n);
    
    for (int i = n - 1; i > n - 1 - m; i--){
        double r = uk/4.0/m;
        if (a[i] < r){
            cout << "No";
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <string>
#include <map>
#include <list>
using namespace std;

// int main() {
//   int n;
//   cin >> n;
//   int a[n],b[n],c[n-1];
//   for(int i = 0; i < n; ++i){
//     cin >> a[i];
//   }
//   for(int i = 0; i < n; ++i){
//     cin >> b[i];
//   }
//   for(int i = 0; i < n-1; ++i){
//     cin >> c[i];
//   }
//   int res=0;
//   for(int i = 0; i < n; ++i){
//     res+=b[a[i]-1];
//     if(a[i]!=n){
//       if(b[a[i]-1] + 1 == b[a[i+1]]-1){
//         res+=c[a[i]-1];
//       }
//     }
//   }
//   cout << res << endl;
// }

int main() {
  int N; cin >> N;
  // input
  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
    --A[i];
  }
  vector<int> B(N);
  for (int i = 0; i < N; ++i) {
    cin >> B[i];
  }
  vector<int> C(N-1);
  for (int i = 0; i < N-1; ++i) {
    cin >> C[i];
  }
  // calc
  int ans = 0;
  for (int i = 0; i < N; ++i) {
    ans += B[A[i]];
    if (i > 0 && A[i] == A[i-1]+1) {
      ans += C[A[i-1]];
    }
  }
  // output
  cout << ans << endl;
}

Measured memory_bytes: 3604
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    str_ = ""
    while n != 0:
        r = n % 2
        if r < 0:
            r += 2
        n = (n-r)//(-2)
        str_ += str(r)
    str_ = str_[::-1]
    if str_ == "":
        str_ = '0'
    print(str_)
if __name__ == '__main__':
  main()


Measured memory_bytes: 5256
#include<iostream>
#include<random>
using namespace std;
int D;
int c[26],s[365][26];
int t[365],now;
int anst[365],ans;
void calc()
{
	int lst[26];
	for(int i=0;i<26;i++)lst[i]=-1;
	now=0;
	for(int i=0;i<D;i++)
	{
		now+=s[i][t[i]];
		lst[t[i]]=i;
		for(int j=0;j<26;j++)now-=c[j]*(i-lst[j]);
	}
}
int change(int d,int q)
{
	int ret=0;
	ret-=s[d][t[d]];
	ret+=s[d][q];
	{
		int r=d+1;
		while(r<D&&t[r]!=t[d])r++;
		int l=d-1;
		while(l>=0&&t[l]!=t[d])l--;
		ret-=c[t[d]]*(r-d)*(d-l);
	}
	{
		int r=d+1;
		while(r<D&&t[r]!=q)r++;
		int l=d-1;
		while(l>=0&&t[l]!=q)l--;
		ret+=c[q]*(r-d)*(d-l);
	}
	return ret;
}
main()
{
	cin>>D;
	for(int i=0;i<26;i++)cin>>c[i];
	for(int i=0;i<D;i++)for(int j=0;j<26;j++)cin>>s[i][j];
	mt19937 rng(114514);
	for(int i=0;i<D;i++)
	{
		anst[i]=t[i]=rng()%26;
	}
	calc();
	ans=now;
	for(int tm=0;tm<4000;tm++)
	{
		int d=rng()%D,q=rng()%26;
		now+=change(d,q);
		t[d]=q;
		for(int k=0;k<1000;k++)
		{
			int d1=rng()%(D-1)+1,d2=rng()%d1;
			int pt1=t[d1],pt2=t[d2];
			int diff=0;
			diff+=change(d1,pt2);
			t[d1]=pt2;
			diff+=change(d2,pt1);
			t[d2]=pt1;
			if(diff>=0)
			{
				now+=diff;
			}
			else
			{
				t[d1]=pt1;
				t[d2]=pt2;
			}
		}
		if(ans<=now)
		{
			ans=now;
			for(int i=0;i<D;i++)anst[i]=t[i];
		}
		else
		{
			now=ans;
			for(int i=0;i<D;i++)t[i]=anst[i];
		}
	}
	for(int i=0;i<D;i++)cout<<anst[i]+1<<endl;
	cerr<<ans<<endl;
}

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

int main() {
  int n;
  cin >> n;
  
  int ans = 0;
  for(int i = 0; i < n; i++){
    int a, b;
    cin >> a >> b;
    ans += b - a + 1;
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 256
// In the name of God

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	cout << (n*(n-1))/2 + (m*(m-1))/2;
	return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

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


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


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


#define ARRAY_MAX 100005
const int INF = 1e9 + 7;
const ll MOD = 1e9 + 7;

int dx4[4] = { 1,0,0,-1 };
int dy4[4] = { 0,1,-1,0 };
int dx2[2] = { 1,0 };
int dy2[2] = { 0,1 };

/******************************************************************************************/
typedef tuple<int,int,int> tpl;


int sum = 0;
string s;


int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);

    ll k;
    cin >> k;

    queue<ll> que;
    for (int i = 1; i < 10; i++)
    {
        que.push(i);
    }
    
    ll cnt = 0;
    ll total = 0;
    while(!que.empty() && cnt < k){

        ll now = que.front();
        que.pop();
        cnt++;
        //cout << "now = " << now << " cnt= " << cnt << endl; 
        if(cnt == k){
            cout << now << endl;
            return 0;
        }

        ll ed = now%10;
        for (int i = max(0LL,ed-1); i <= min(ed+1,9LL); i++)
        {
            //cout << i << " " << now*10+i << endl;
            que.push(now*10+i);
            //total ++;
        }
    }


	return 0;
}



Measured memory_bytes: 1792
/*
数据不清空，爆零两行泪。
多测不读完，爆零两行泪。
边界不特判，爆零两行泪。
贪心不证明，爆零两行泪。
D P 顺序错，爆零两行泪。
大小少等号，爆零两行泪。
变量不统一，爆零两行泪。
越界不判断，爆零两行泪。
调试不注释，爆零两行泪。
溢出不 l l，爆零两行泪。
*/
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=15;
int n,m;
int tb[N][N];//邻接矩阵 
int sum[1<<N]; 
int tmp[1<<N][N],dp[1<<N][N];
void prt_bitmsk(int x){ 
	for(int i=0;i<n;i++)cout<<!!(x&1<<i);
}
int main(){
	cin>>n>>m;
	int tot=0;
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		x--;y--;
		tb[x][y]=tb[y][x]=z;
		tot+=z;
	}
	for(int i=0;i<1<<n;i++){//预处理sum 
		for(int j=0;j<n;j++)if(i&1<<j)for(int k=j+1;k<n;k++)if(i&1<<k)
			sum[i]+=tb[j][k];
//		printf("sum[");prt_bitmsk(i);printf("]=%d\n",sum[i]);
	}
	for(int i=0;i<1<<n;i++)for(int j=0;j<n;j++)dp[i][j]=tmp[i][j]=-inf;//初始化 
	for(int i=0;i<1<<n;i++)if(i&1)for(int j=0;j<n;j++)if(i&1<<j){//DP 
		if(j)//非边界 
			for(int k=i^1<<j^1;;k=k-1&(i^1<<j^1)){//枚举j下面挂的点集k 
				dp[i][j]=max(dp[i][j],sum[k|1<<j]+tmp[i^k^1<<j][j]);//状态转移方程 
				if(!k)break;
			}
		else//边界 
			dp[i][j]=sum[i];
//		printf("dp[");prt_bitmsk(i);printf("][%d]=%d\n",j,dp[i][j]);
		for(int k=0;k<n;k++)if(!(i&1<<k))//更新与dp[i][j]有关的所有tmp[i][k] 
			if(tb[j][k])
				tmp[i][k]=max(tmp[i][k],dp[i][j]+tb[j][k]);
	}
	cout<<tot-dp[(1<<n)-1][n-1];//目标 
	return 0;
}
/*1
4 6
1 2 100
3 1 100
2 4 100
4 3 100
1 4 100
3 2 100
*/
/*2
2 1
1 2 1
*/
/*3
15 22
8 13 33418
14 15 55849
7 10 15207
4 6 64328
6 9 86902
15 7 46978
8 14 53526
1 2 8720
14 12 37748
8 3 61543
6 5 32425
4 11 20932
3 12 55123
8 2 45333
9 12 77796
3 9 71922
12 15 70793
2 4 25485
11 6 1436
2 7 81563
7 11 97843
3 1 40491
*/

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


void solve(long long N, long long M, long long C, std::vector<long long> B, std::vector<std::vector<long long>> A){
    int counter = 0;
    for(int i = 0; i < N; i++) {
        vector<long long> a = A[i];
        long long prosum = C;
        for (int j = 0; j < M; j++) {
            prosum += a[j] * B[j];
        }
        if (prosum > 0) {
           counter += 1;
        }
    }
    cout << counter << endl;
}

// Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long M;
    scanf("%lld",&M);
    long long C;
    scanf("%lld",&C);
    std::vector<long long> B(M);
    for(int i = 0 ; i < M ; i++){
        scanf("%lld",&B[i]);
    }
    std::vector<std::vector<long long>> A(N, std::vector<long long>(M));
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < M ; j++){
            scanf("%lld",&A[i][j]);
        }
    }
    solve(N, M, C, std::move(B), std::move(A));
    return 0;
}


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

int main()
{
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    int ans = 0;

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

    sort(p.begin(), p.end());

    for (int i = 0; i < k; i++)
    {
        ans += p[i];
    }

    cout << ans << endl;
}

Measured memory_bytes: 3624
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = map(int, input().split())
P = list(map(int, input().split()))
P = [p - 1 for p in P]
uf = UnionFind(N)
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    uf.union(x, y)
ans = 0
for i, p in enumerate(P):
    if uf.same(p, i):
        ans += 1
print(ans)

Measured memory_bytes: 13940
using System;
using System.Collections.Generic;
using System.Linq;


namespace AOJ0003
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = Convert.ToInt32(Console.ReadLine());
            for (int i = 0; i < N; i++)
            {
                var s = Console.ReadLine();
                var ss = s.Split(' ');
                var q = ss.ToList().Select(str => Convert.ToInt32(str));

                var qq = q.ToList();
                qq.Sort();
                
                

              Console.WriteLine(qq.ElementAt(2)*qq.ElementAt(2) ==
                                  qq.ElementAt(1)*qq.ElementAt(1) + qq.ElementAt(0)*qq.ElementAt(0)
                                      ? "YES"
                                      : "NO");
            }

        }
    }
}

Measured memory_bytes: 5992
#include <bits/stdc++.h>
#define drep(i,cc,n) for(int i=(cc);i<=(n);++i)
#define rep(i,n) drep(i,0,n-1)
#define drrep(i,cc,n) for(int i=(cc);i>=(n);--i)
#define rrep(i,n) drrep(i,0,n-1)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,v.size())if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define arrprint(v,n) rep(i,n)if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define matprint(v,n,m) rep(i,n){rep(j,m){cout << v[i][j] << " ";}cout << endl;}
#define SORT(v) sort(v.begin(), v.end())
#define REV(v) reverse(v.begin(), v.end())
using namespace std;
const int mod=1000000007;
const int INF=1001001001;
using ll = long long;
using P = pair<int,int>;
template<typename T>
using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; //小さいものから取り出す

int d;
vector<int> c(26);
vector<vector<int>> s;
vector<int> t;
vector<int> last(26, -1);
ll best = 0;

ll score(){
    ll res = 0;
    rep(i,d){
        res += s[i][t[i]];
        last[t[i]] = i;
        rep(j,26) res -= c[i] * (i - last[j]);
    }
    return res;
}

int main(){
    random_device seed;
    mt19937 mt(seed());
    uniform_int_distribution<int> rnd(0,25);

    cin >> d;
    rep(i,26) cin >> c[i];
    s.resize(d);
    rep(i,d)s[i].resize(26);
    rep(i,d)rep(j,26) cin >> s[i][j];
    t.resize(d);
    rep(i,d) t[i] = i%26;
    best = score();
    rep(i,10){
        vector<int> now(d);
        rep(i,d)now[i] = rnd(mt);
        ll now_s = score();
        if(best < now_s){
            best = now_s;
            swap(t,now);
        }
    }


    // cout << score() << endl;
    rep(i,d)cout << t[i]+1 << endl;

    // cout << ans << endl;
//  printf("%.10f\n",ans);

    return 0;
}

Measured memory_bytes: 3688
import math
def solve():
    n = int(input())

    ans = 0
    for x in calc_divisors(n):
        if x == 1:
            continue
        tmp = n
        while tmp % x == 0:
            tmp /= x
        tmp %= x
        if tmp == 1:
            ans += 1
    
    ans += len(calc_divisors(n-1)) - 1

    print(ans)

def calc_divisors(n):
    divisors = []
    for i in range(1,int(math.sqrt(n)+1)):
        if n % i == 0:
            divisors.append(i)
            if (i*i != n):
                divisors.append(n//i)
    return divisors

if __name__ == '__main__':
    solve()

Measured memory_bytes: 39152
//
#include <vector>
#include <set>
#include <map>
#include <array>
#include <iostream>
#include <cstdio>
#include <cstdint>
#include <algorithm>
#include <numeric>
#include <bitset>
#include <iomanip>
//
using ll = long long;
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);++i)
#define outD(fpv) cout << setprecision(20) << fpv << endl;
inline void yes(bool cond) { cond ? puts("Yes") : puts("No"); }
inline void YES(bool cond) { cond ? puts("YES") : puts("NO"); }
template<typename Type> inline void chmin(Type& a, Type b) { if (a > b) a = b; }
template<typename Type> inline void chmax(Type& a, Type b) { if (a < b) a = b; }
template<typename Arr, typename Type> inline void fill(Arr& arr, Type v) { std::fill(arr.begin(), arr.end(), v); }
template<typename Type> inline void sort(Type& arr) { std::sort(arr.begin(), arr.end()); }
template<typename Type> inline void reverse(Type& arr) { reverse(arr.begin(), arr.end()); }
template<typename Type> inline Type nth(vector<Type>& arr, size_t pos) { std::nth_element(arr.begin(), arr.begin() + pos, arr.end()); return arr[pos]; }
template<typename Type> inline void unique(Type& arr) { sort(arr); arr.erase(unique(arr.begin(), arr.end()), arr.end()); }
constexpr ll INF_I = std::numeric_limits<ll>::max();
constexpr ll BIGP = 1e9+7;
constexpr double INF_F = std::numeric_limits<float>::infinity();
constexpr double PI = 3.14159265358979323846L;
using P = pair<ll, ll>;
//
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    //
    ll L, R;
    cin >> L >> R;
    //
    ll ans = 0;
    if (R - L > 2019)
    {
        ans = 0;
    }
    else
    {
        ans = INF_I;
        for (ll i=L;i<=R;++i)
        {
            for (ll j = i+1; j <= R; ++j)
            {
                chmin(ans, (i * j) % 2019);
            }
        }
    }
    cout << ans;


    //
    return 0;
}

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

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

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

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
  // 入力
  int N;
  cin >> N;

  int ans = 0;
  for (int i = 1; i <= N; i++) {
    if (!(i & 1)) continue;
    int cnt = 0;
    for (int j = 1; j <= i; j++) {
      if (i % j == 0) cnt++;
    }
    if (cnt == 8) ans++;
  }

  // 解答
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
	int a,b,c;
	
	scanf("%d %d %d",&a,&b,&c);
	
	if(a+b==c)
		printf("Yes\n");
	else if(a+c==b)
		printf("Yes\n");
	else if(b+c==a)
		printf("Yes\n");
	else printf("No");
	
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
int main(){
  int i,j,n;
  cin >> n;
  long long a[n];
  for(i=0;i<n;i++){
    cin >> a[i];
  }

  long long allsum=0;
  for(i=0;i<n;i++){
    allsum+=a[i];
  }
  allsum/=2;

  long long l2sum[n];
  l2sum[0]=a[0];
  l2sum[1]=a[1];
  for(int i=2;i<n;i++){
    l2sum[i]=l2sum[i-2]+a[i];
  }
 
  long long r2sum[n];
  r2sum[n-1]=a[n-1];
  r2sum[n-2]=a[n-2];
  for(int i=n-3;i>=0;i--){
    r2sum[i]=r2sum[i+2]+a[i];
  }
  
  for(i=0;i<n;i++){
    cout<<2*(allsum-(i-2>=0 ? l2sum[i-2] : 0)-(i+1<n ? r2sum[i+1] :0))<<' ';
  }
  return 0;
}


Measured memory_bytes: 3712