QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #810395 | #9552. The Chariot | frankly6 | WA | 19ms | 3820kb | C++17 | 5.9kb | 2024-12-11 21:58:40 | 2024-12-11 21:58:41 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cassert>
using namespace std;
struct HighPrecision
{
typedef unsigned long long LL;
static const int BASE=100000000;
static const int WIDTH=8;
vector<int>s;
HighPrecision&clean()
{
while(!s.back()&&s.size()>1)
s.pop_back();
return *this;
}
HighPrecision(LL num=0)
{
*this=num;
}
HighPrecision(string s)
{
*this=s;
}
HighPrecision&operator=(LL num)
{
s.clear();
do
{
s.push_back(num%BASE);
num/=BASE;
}while(num>0);
return *this;
}
HighPrecision&operator=(const string&str)
{
s.clear();
int x,len=(str.length()-1)/WIDTH+1;
for(int i=0;i<len;i++)
{
int end=str.length()-i*WIDTH;
int start=max(0,end-WIDTH);
sscanf(str.substr(start,end-start).c_str(),"%d",&x);
s.push_back(x);
}
return(*this).clean();
}
HighPrecision operator + (const HighPrecision& b) const {
HighPrecision c; c.s.clear();
for (int i = 0, g = 0; ; i++) {
if (g == 0 && i >= s.size() && i >= b.s.size()) break;
int x = g;
if (i < s.size()) x += s[i];
if (i < b.s.size()) x += b.s[i];
c.s.push_back(x % BASE);
g = x / BASE;
}
return c;
}
HighPrecision operator - (const HighPrecision& b) const {
assert(b <= *this);
HighPrecision c; c.s.clear();
for (int i = 0, g = 0; ; i++) {
if (g == 0 && i >= s.size() && i >= b.s.size()) break;
int x = s[i] + g;
if (i < b.s.size()) x -= b.s[i];
if (x < 0) {g = -1; x += BASE;} else g = 0;
c.s.push_back(x);
}
return c.clean();
}
HighPrecision operator * (const HighPrecision& b) const {
int i, j; LL g;
vector<LL> v(s.size()+b.s.size(), 0);
HighPrecision c; c.s.clear();
for(i=0;i<s.size();i++)
for(j=0;j<b.s.size();j++)
v[i+j]+=LL(s[i])*b.s[j];
for (i = 0, g = 0; ; i++) {
if (g ==0 && i >= v.size()) break;
LL x = v[i] + g;
c.s.push_back(x % BASE);
g = x / BASE;
}
return c.clean();
}
HighPrecision operator / (const HighPrecision& b) const {
assert(b > 0);
HighPrecision c = *this;
HighPrecision m;
for (int i = s.size()-1; i >= 0; i--) {
m = m*BASE + s[i];
c.s[i] = bsearch(b, m);
m -= b*c.s[i];
}
return c.clean();
}
HighPrecision operator % (const HighPrecision& b) const {
HighPrecision c = *this;
HighPrecision m;
for (int i = s.size()-1; i >= 0; i--) {
m = m*BASE + s[i];
c.s[i] = bsearch(b, m);
m -= b*c.s[i];
}
return m;
}
int bsearch(const HighPrecision& b, const HighPrecision& m) const{
int L=0, R=BASE-1, ans=0;
while(L<=R)
{
int mid=(L+R)>>1;
if(b*mid<=m) ans=mid, L=mid+1;
else R=mid-1;
}
return ans;
}
HighPrecision& operator += (const HighPrecision& b) {*this = *this + b; return *this;}
HighPrecision& operator -= (const HighPrecision& b) {*this = *this - b; return *this;}
HighPrecision& operator *= (const HighPrecision& b) {*this = *this * b; return *this;}
HighPrecision& operator /= (const HighPrecision& b) {*this = *this / b; return *this;}
HighPrecision& operator %= (const HighPrecision& b) {*this = *this % b; return *this;}
bool operator < (const HighPrecision& b) const {
if (s.size() != b.s.size()) return s.size() < b.s.size();
for (int i = s.size()-1; i >= 0; i--)
if (s[i] != b.s[i]) return s[i] < b.s[i];
return false;
}
bool operator >(const HighPrecision& b) const{return b < *this;}
bool operator<=(const HighPrecision& b) const{return !(b < *this);}
bool operator>=(const HighPrecision& b) const{return !(*this < b);}
bool operator!=(const HighPrecision& b) const{return b < *this || *this < b;}
bool operator==(const HighPrecision& b) const{return !(b < *this) && !(b > *this);}
};
ostream& operator << (ostream& out, const HighPrecision& x) {
out << x.s.back();
for (int i = x.s.size()-2; i >= 0; i--) {
char buf[20];
sprintf(buf, "%08d", x.s[i]);
for (int j = 0; j < strlen(buf); j++) out << buf[j];
}
return out;
}
istream& operator >> (istream& in, HighPrecision& x) {
string s;
if (!(in >> s)) return in;
x = s;
return in;
}
HighPrecision min(HighPrecision a, HighPrecision b) {return a<=b?a:b;}
int main()
{
// freopen("testdata.in","r",stdin);
// HugeInt t1("0"), t2("100");
// cout << t1/t2 << '\n';
int T;
cin >> T;
while(T--)
{
HighPrecision A, B, C, X, Y, D;
cin >> A >> B >> C >> X >> Y >> D;
// cout << A << " " << B << " " << C << " " << X << " " << Y << " " << D << " " << '\n';
HighPrecision c1(0), c2(0), c3(0);
if(D<=X) {cout << A << '\n'; continue;}
if(D<=X+Y) c1=A*B+(D-X);
else c1=A+B*Y+C*(D-X-Y);
HighPrecision cA, nA, left;
cA=(D/X)*A;
nA=D/X;
left=D-(nA*X);
if(nA*Y<left) c2 = cA+min(nA*Y*B+(left-nA*Y)*C, Y*B+(left-Y)*C);
else if(Y<=left) c2 = cA+min(left*B, Y*B+(left-Y)*C);
else c2 = cA+(left*B);
c2=min(c2,cA+A);
HighPrecision bD=X+Y, bC=A+(B*Y), cAB, nAB;
cAB=(D/bD)*bC;
nAB=D/bD;
left=D-(nAB*bD);
if(left<X) c3 = cAB+A-min(nAB*Y,X-left)*B;
else c3 = cAB+A+(left-X)*B;
if(D>bD) c3 = min(c3,cAB+(C*left));
cout << min(c1,min(c2,c3)) << '\n';
}
return (0-0);
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3820kb
input:
5 160 27 41 3 12 3 160 27 41 3 12 4 160 27 41 3 12 99 1 999 999 1 99 999 999 999 1 1 99 9999999999999999
output:
160 187 3226 999 10000000000099799
result:
ok 5 lines
Test #2:
score: -100
Wrong Answer
time: 19ms
memory: 3652kb
input:
2077 63 88 64 47 55 88 4 75 38 53 33 41 41 1 28 6 13 100 57 88 77 35 5 48 100 36 97 24 93 87 57 25 26 84 62 18 29 11 33 88 86 71 33 16 7 4 73 68 50 65 72 14 43 78 15 31 72 42 39 29 31 10 76 58 35 89 39 55 99 11 16 82 21 18 57 44 80 16 38 31 99 58 59 69 24 22 69 76 14 83 96 40 56 31 14 36 75 84 27 57...
output:
126 4 310 114 400 57 29 561 300 15 62 312 21 76 48 192 150 130 97 636 76 32 112 180 39 138 36 605 30 23 88 76 285 20 330 325 174 128 32 36 1 36 30 24 192 170 17 88 83 102 140 86 52 81 25 44 8 21 180 49 51 145 55 82 31 85 156 70 158 21 84 48 156 51 145 174 156 86 2 73 83 5 200 117 44 6 152 58 122 26 ...
result:
wrong answer 455th lines differ - expected: '229', found: '167'